Access the full text.
Sign up today, get an introductory month for just $19.
M. Hajiaghayi, K. Jain (2006)
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
Chaitanya Swamy, Amit Kumar (2002)
Primal-Dual Algorithms for Connected Facility Location Problems
S. Rajagopalan, V. Vazirani (1999)
On the bidirected cut relaxation for the metric Steiner tree problem
A. Frank, É. Tardos (1987)
An application of simultaneous diophantine approximation in combinatorial optimizationCombinatorica, 7
(1979)
Computers and intractability
N. Alon, J. Spencer (1992)
The Probabilistic Method
J. Könemann, David Pritchard, Kunlun Tan (2007)
A partition-based relaxation for Steiner treesMathematical Programming, 127
Romeo Rizzi (2003)
On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristicInf. Process. Lett., 86
S. Dreyfus, Robert Wagner (1971)
The steiner problem in graphsNetworks, 1
F. Eisenbrand, F. Grandoni, G. Oriolo, M. Skutella (2005)
New Approaches for Virtual Private Network DesignSIAM J. Comput., 37
Mohit Singh, Kunal Talwar (1997)
Approximation AlgorithmsProceedings of the National Academy of Sciences of the United States of America, 94 24
C. Chekuri, F. Shepherd (2008)
Approximate Integer Decompositions for Undirected Network Design ProblemsSIAM J. Discret. Math., 23
M. Goemans, Young-Soo Myung (1993)
A catalog of steiner tree formulationsNetworks, 23
L. Cijan (1979)
A polynomial algorithm in linear programming
Anupam Gupta, Amit Kumar, Iit Delhi, Martin P, A Kumar (2007)
Approximation via Cost Sharing: Simpler and Better Approximation Algorithms for Network Design
F. Eisenbrand, F. Grandoni (2005)
An improved approximation algorithm for virtual private network design
H. Prömel, A. Steger (2000)
A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3J. Algorithms, 36
Al Borchers, D. Du (1995)
The k-Steiner ratio in graphs
(1967)
Optimum branchings
K. Jain (1998)
A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 21
A. Zelikovsky (1993)
An 11/6-approximation algorithm for the network steiner problemAlgorithmica, 9
G. Robins, A. Zelikovsky (2005)
Tighter Bounds for Graph Steiner Tree ApproximationSIAM J. Discret. Math., 19
David Johnson (1982)
The NP-Completeness Column: An Ongoing GuideJ. Algorithms, 4
M. Goemans, David Williamson (1992)
A general approximation technique for constrained forest problemsSIAM J. Comput., 24
M. Bern, P. Plassmann (1989)
The Steiner Problem with Edge Lengths 1 and 2Inf. Process. Lett., 32
M. Grötschel, L. Lovász, A. Schrijver (1981)
The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1
S. Janson, Tomasz Łuczak, A. Rucinski (2011)
Wiley‐Interscience Series in Discrete Mathematics and Optimization
Anupam Gupta, J. Kleinberg, Amit Kumar, R. Rastogi, B. Yener (2001)
Provisioning a virtual private network: a network design problem for multicommodity flow
M. Garey, David Johnson (1977)
The Rectilinear Steiner Tree Problem is NP CompleteSIAM Journal of Applied Mathematics, 32
M. Charikar, S. Guha (1999)
Improved Combinatorial Algorithms for Facility Location Problems ∗
Kunal Talwar (2002)
The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap
F. Schlenk (2005)
Proof of Theorem 3
Aaron Archer, M. Bateni, M. Hajiaghayi, H. Karloff (2009)
Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP2009 50th Annual IEEE Symposium on Foundations of Computer Science
B. Wu, K. Chao (2005)
Steiner Minimal Trees
Exa Corporation, Brown University, University California-Davis (1991)
When trees collide: an approximation algorithm for the generalized Steiner problem on networksSIAM J. Comput., 24
(1967)
J. Edmonds. Optimum branchings. J. Res. Nat. Bur. Standards
F. Eisenbrand, F. Grandoni, T. Rothvoss, G. Schäfer (2008)
Approximating connected facility location problems via random facility sampling and core detouring
D. Mölle, Stefan Richter, P. Rossmanith (2006)
A Faster Algorithm for the Steiner Tree Problem
F. Grandoni, G. Italiano (2006)
Improved Approximation for Single-Sink Buy-at-Bulk
Tobias Polzin, Siavash Daneshmand (2003)
On Steiner trees and minimum spanning trees in hypergraphsOper. Res. Lett., 31
J. Bang-Jensen, A. Frank, B. Jackson (1995)
Preserving and Increasing Local Edge-Connectivity in Mixed GraphsSIAM J. Discret. Math., 8
W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver (1997)
Combinatorial optimization
Sanjeev Arora (1998)
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJ. ACM, 45
F. Eisenbrand, F. Grandoni, T. Rothvoss, G. Schäfer (2010)
Connected facility location via random facility sampling and core detouringJ. Comput. Syst. Sci., 76
H. Prömel, A. Steger (2002)
The Steiner Tree Problem
M. Chlebík, J. Chlebíková (2008)
The Steiner tree problem on graphs: Inapproximability resultsTheor. Comput. Sci., 406
G. Borradaile, Claire Mathieu, P. Klein (2007)
A polynomial-time approximation scheme for Steiner tree in planar graphs
Deeparnab Chakrabarty, Nikhil Devanur, V. Vazirani (2008)
New geometry-inspired relaxations and algorithms for the metric Steiner tree problemMathematical Programming, 130
Marek Karpinski, A. Zelikovsky (1997)
New Approximation Algorithms for the Steiner Tree ProblemsJournal of Combinatorial Optimization, 1
O. Grumberg, D. Peled, B. Korte, J. Vygen
Combinatorial Optimization-Theory and Algorithms by
An Improved LP-based Approximation for Steiner Tree Â— Institute of Mathematics, EPFL Lausanne, Switzerland JarosÃ…Â‚aw Byrka jaroslaw.byrka@ep Â‚.ch Thomas RothvoÃƒÂŸ grandoni@disp.uniroma2.it Institute of Mathematics, EPFL Lausanne, Switzerland University of Tor Vergata Rome, Italy Fabrizio Grandoni Â¡ Institute of Mathematics, EPFL Lausanne, Switzerland Laura SanitÃƒ Ã‚Â§ thomas.rothvoss@ep Â‚.ch laura.sanita@ep Â‚.ch ABSTRACT The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, Ând a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA Â™05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,RajagopalanSODA Â™99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directedcomponent cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get an introductory month for just $19.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.