Article

Approximating the smallest k-edge connected spanning subgraph by LP-rounding

Authors:

Harold N. Gabow,

Michel X. Goemans,

Éva Tardos,

David P. WilliamsonAuthors Info & Claims

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 562 - 571

Published: 23 January 2005 Publication History

Get Access

Abstract

The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k-edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. These results prove that the smallest k-ECSS problem gets easier to approximate as k tends to infinity. They also show the integrality gap of the natural linear program is at most 1 + 2/k, for both directed and undirected graphs.

References

[1]

J. Cheriyan and R. Thurimella, Approximating minimum-size k-connected spanning subgraphs via matching, SIAM J. Comput., 30, 2 (2000), pp. 528--560.

Digital Library

Google Scholar

[2]

G. Cornuéjols, J. Fonlupt and D. Naddef, The traveling salesman problem on a graph and some related integer polyhedra, Math. Programming, 33 (1985), pp. 1--27.

Google Scholar

[3]

C. G. Fernandes, A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem, J. Algorithms, 28, 1 (1998), pp. 105--124.

Digital Library

Google Scholar

[4]

A. Frank, Submodular functions in graph theory, Discrete Math., 111 (1993), pp. 231--243.

Digital Library

Google Scholar

[5]

H. N. Gabow, Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph, Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms, 2003, pp. 460--469.

Digital Library

Google Scholar

[6]

H. N. Gabow, Special edges, and approximating the smallest directed k-edge connected spanning subgraph, Proc. 15th Annual ACM-SIAM Symp. on Discrete Algorithms, 2004, pp. 227--236.

Digital Library

Google Scholar

[7]

H. N. Gabow, On the difficulty of k-connected spanning subgraph problems, unpublished notes.

Google Scholar

[8]

H. N. Gabow, On the L∞-norm of extreme points for crossing supermodular directed network LPs, manuscript.

Google Scholar

[9]

K. Jain, A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica 21 (2001), pp. 39--60.

Google Scholar

[10]

D. R. Karger, Random sampling in cut, flow, and network design problems, Math. of OR 24, 2 (1999), pp. 383--413.

Crossref

Google Scholar

[11]

S. Khuller and B. Raghavachari, Improved approximation algorithms for uniform connectivity problems, J. Algorithms 21, 2 (1996), pp. 434--450.

Digital Library

Google Scholar

[12]

V. Melkonian and E. Tardos, Algorithms for a network design problem with crossing supermodular demands, Networks 43, 4 (2004), pp. 256--265.

Digital Library

Google Scholar

[13]

V. V. Vazirani, Approximation Algorithms, Springer-Verlag, NY, 2001.

Digital Library

Google Scholar

Cited By

View all

Gabow HGallagher STeng S(2008)Iterated rounding algorithms for the smallest k-edge connected spanning subgraphProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347143(550-559)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347143
Fakcharoenphol JLaekhanukit BLadner RDwork C(2008)An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problemProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374401(153-158)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374401
Gubbala PRaghavachari B(2007)A 4/3-approximation algorithm for minimum 3-edge-connectivityProceedings of the 10th international conference on Algorithms and Data Structures10.5555/2394893.2394901(39-51)Online publication date: 15-Aug-2007
https://dl.acm.org/doi/10.5555/2394893.2394901
Show More Cited By

Approximating the smallest k-edge connected spanning subgraph by LP-rounding
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Functional analysis
2. Theory of computation

Recommendations

Approximating the smallest k-edge connected spanning subgraph by LP-rounding

The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k-edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A ...
Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph

We present the best known algorithms for approximating the minimum-size undirected $k$-edge connected spanning subgraph. For simple graphs our approximation ratio is $1+ {1}/(2k) + O({1}/{k^2})$. The more precise version of this bound requires $k\ge 7$, ...
An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

This paper gives a 3/2 approximation algorithm for the smallest 3-edge connected spanning subgraph of an undirected multigraph. The previous best algorithm of Khuller and Raghavachari [8] has approximation ratio 5/3. The algorithm of Cheriyan and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

January 2005

1205 pages

ISBN:0898715857

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2005

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
433
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gabow HGallagher STeng S(2008)Iterated rounding algorithms for the smallest k-edge connected spanning subgraphProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347143(550-559)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347143
Fakcharoenphol JLaekhanukit BLadner RDwork C(2008)An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problemProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374401(153-158)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374401
Gubbala PRaghavachari B(2007)A 4/3-approximation algorithm for minimum 3-edge-connectivityProceedings of the 10th international conference on Algorithms and Data Structures10.5555/2394893.2394901(39-51)Online publication date: 15-Aug-2007
https://dl.acm.org/doi/10.5555/2394893.2394901
Kortsarz GNutov Z(2006)Tight approximation algorithm for connectivity augmentation problemsProceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part I10.1007/11786986_39(443-452)Online publication date: 10-Jul-2006
https://dl.acm.org/doi/10.1007/11786986_39
Dragan FYan C(2006)Network flow spannersProceedings of the 7th Latin American conference on Theoretical Informatics10.1007/11682462_39(410-422)Online publication date: 20-Mar-2006
https://dl.acm.org/doi/10.1007/11682462_39

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Approximating the smallest k-edge connected spanning subgraph by LP-rounding

Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph

An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph