Approximating the smallest k-edge connected spanning subgraph by LP-rounding
作者： Michel X. Goemans , Harold N. Gabow , Éva Tardos , David P. Williamson
DOI: 10.1002/NET.V53:4
关键词: Multigraph 、 Discrete mathematics 、 Connectivity 、 Graph (abstract data type) 、 Mathematics 、 Approximation algorithm 、 Directed graph 、 Upper and lower bounds 、 Round-off error 、 Combinatorics 、 Rounding
摘要: The smallest k-ECSS problem is, given a graph along with an integer k, find spanning subgraph that is k-edge connected and contains the fewest possible number of edges. We examine natural approximation algorithm based on rounding LP solution. A tight bound ratio 1 + 3-k for undirected graphs k > odd, 2-k even, directed arbitrary. Using iterated improves first upper to 2-k. On hardness side we show some absolute constant c 0, any ≥ 2 (k 1), polynomial-time approximating (directed) multigraphs within c-k would imply P = NP. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009
sci-hub.st 参考文章(11)
Harold N. Gabow, An Improved Analysis for Approximating the Smallest k -Edge Connected Spanning Subgraph of a Multigraph SIAM Journal on Discrete Mathematics. ,vol. 19, pp. 1- 18 ,(2005) , 10.1137/S0895480102414910
Vardges Melkonian, �va Tardos, Algorithms for a network design problem with crossing supermodular demands Networks. ,vol. 43, pp. 256- 265 ,(2004) , 10.1002/NET.20005
Cristina G Fernandes, A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem Journal of Algorithms. ,vol. 28, pp. 105- 124 ,(1998) , 10.1006/JAGM.1998.0931
Samir Khuller, Balaji Raghavachari, Improved Approximation Algorithms for Uniform Connectivity Problems Journal of Algorithms. ,vol. 21, pp. 434- 450 ,(1996) , 10.1006/JAGM.1996.0052
Gérard Cornuéjols, Jean Fonlupt, Denis Naddef, The traveling salesman problem on a graph and some related integer polyhedra Mathematical Programming. ,vol. 33, pp. 1- 27 ,(1985) , 10.1007/BF01582008
András Frank, Submodular functions in graph theory Discrete Mathematics. ,vol. 111, pp. 231- 243 ,(1993) , 10.1016/0012-365X(93)90158-P
Harold N. Gabow, On the L ∞ -norm of extreme points for crossing supermodular directed network LPs integer programming and combinatorial optimization. ,vol. 110, pp. 111- 144 ,(2007) , 10.1007/S10107-006-0061-9
Joseph Cheriyan, Ramakrishna Thurimella, Approximating Minimum-Size k -Connected Spanning Subgraphs via Matching SIAM Journal on Computing. ,vol. 30, pp. 528- 560 ,(2000) , 10.1137/S009753979833920X
David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems Mathematics of Operations Research. ,vol. 24, pp. 383- 413 ,(1999) , 10.1287/MOOR.24.2.383
Kamal Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem Combinatorica. ,vol. 21, pp. 39- 60 ,(2001) , 10.1007/S004930170004