Approximating minimum-cost edge-covers of crossing biset-families

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Part of this paper appeared in the preliminary version [16]. An ordered pair Ŝ = (S, S +) of subsets of a groundset V is called a biset if S ⊆ S+; (V S +;V S) is the co-biset of Ŝ. Two bisets X̂, Ŷ intersect if X X ∩ Y ≠ ∅ and cross if both X ∩ Y ≠ ∅ and X + ∪ Y + ≠= V. The intersection and the union of two bisets X̂,Ŷ are defined by X̂ ∩ Ŷ = (X ∩ Y, X+ ∩ Y+) and X ∪ Y = (X ∪ Y,X+ ∪Y+). A biset-family F is crossing (intersecting) if X̂ ∩ Ŷ, X̂ ∪ Ŷ ε F for any X̂, Ŷ ε F that cross (intersect). A directed edge covers a biset Ŝ if it goes from S to V S +. We consider the problem of covering a crossing biset-family F by a minimum-cost set of directed edges. While for intersecting F, a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing F is not yet understood, as it includes several NP-hard problems, for which a poly-logarithmic approximation was discovered only recently or is not known. Let us say that a biset-family F is k-regular if X̂ ∩ Ŷ, X̂ ∪ Ŷ ε F for any X̂,Ŷ ε F with {pipe}V (X∪Y)≥k+1 that intersect. In this paper we obtain an O(log {pipe}V{pipe})-approximation algorithm for arbitrary crossing F; if in addition both F and the family of co-bisets of F are k-regular, our ratios are: (Formula presented.) Using these generic algorithms, we derive for some network design problems the following approximation ratios: (Formula presented.) for Subset k-Connected Subgraph when all edges with positive cost have their endnodes in the subset.

שפה מקוריתאנגלית
עמודים (מ-עד)95-114
מספר עמודים20
כתב עתCombinatorica
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - פבר׳ 2014

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating minimum-cost edge-covers of crossing biset-families'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי