Computer Science – Discrete Mathematics
Scientific paper
2010-04-12
Computer Science
Discrete Mathematics
Appeared at WAOA 2010
Scientific paper
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 subset F of E such that (V, F) is k-edge-connected. We show there is a constant eps > 0 so that for all k > 1, finding a (1 + eps)-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 + Theta(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.
No associations
LandOfFree
k-Edge-Connectivity: Approximation and LP Relaxation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with k-Edge-Connectivity: Approximation and LP Relaxation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and k-Edge-Connectivity: Approximation and LP Relaxation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-262538