k-edge-connectivity: approximation and LP relaxation

DOI10.1007/978-3-642-18318-8_20zbMATH Open1314.68402arXiv1004.1917OpenAlexW1752817158MaRDI QIDQ3075464FDOQ3075464

Authors:

Publication date: 15 February 2011

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1004.1917

Recommendations

• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.
• scientific article; zbMATH DE number 2011856
• Iterated rounding algorithms for the smallest \(k\)-edge connected spanning subgraph

zbMATH Keywords

approximation algorithmsinapproximabilitynetwork designedge-connectivitylinear programsHeld-Karp relaxation

Mathematics Subject Classification ID

Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40)

Cited In (7)

• Title not available (Why is that?)
• A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Multicommodity flow in trees: packing via covering and iterated relaxation

This page was built for publication: \(k\)-edge-connectivity: approximation and LP relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3075464)