Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
k-Edge-Connectivity: Approximation and LP Relaxation
verfasst von : David Pritchard
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the
k
-edge-connected spanning subgraph problem we are given a graph (
V
,
E
) and costs for each edge, and want to find a minimum-cost
F
⊂
E
such that (
V
,
F
) is
k
-edge-connected. We show there is a constant
ε
> 0 so that for all
k
> 1, finding a (1 +
ε
)-approximation for
k
-ECSS is
NP
-hard, establishing a gap between the unit-cost and general-cost versions. Next, we consider the
multi-subgraph
cousin of
k
-ECSS, in which we purchase a
multi-subset
F
of
E
, with unlimited parallel copies available at the same cost as the original edge. We conjecture that a (1 + Θ(1/
k
))-approximation algorithm exists, and we describe an approach based on graph decompositions applied to its natural linear programming (LP) relaxation. The LP is essentially equivalent to the Held-Karp LP for TSP and the undirected LP for Steiner tree. We give a family of extreme points for the LP which are more complex than those previously known.