Jaroslaw Byrka
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, find 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,Rajagopalan-SODA'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 directed-component 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 a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+ε<1.39 approximation for Steiner tree. As a byproduct of our analysis, we show that the integrality gap of our LP is at most $1.55$, hence answering to the mentioned open question. This might have consequences for a number of related problems.
- A. Agrawal, P. Klein, and R. Ravi. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3): 440--456, 1995. Google Scholar
Digital Library
- N. Alon and J. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., Hoboken, NJ, third edition, 2008.Google Scholar
- A. Archer, M. Bateni, M. Hajiaghayi, and H. Karloff. Improved approximation algorithms for prize-collecting Steiner tree and TSP. In FOCS, pages 427--436, 2009. Google ScholarDigital Library
- S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753--782, 1998. Google ScholarDigital Library
- M. Bern and P. Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4):171--176, 1989. Google ScholarDigital Library
- A. Borchers and D. Du. The k-Steiner ratio in graphs. SIAM Journal on Computing, 26(3):857--869, 1997. Google ScholarDigital Library
- G. Borradaile, C. Kenyon-Mathieu, and P. Klein. A polynomial-time approximation scheme for Steiner tree in planar graphs. In SODA, pages 1285--1294, 2007. Google ScholarDigital Library
- D. Chakrabarty, N. R. Devanur, and V. V. Vazirani. New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. In IPCO, pages 344--358, 2008. Google ScholarDigital Library
- M. Charikar and S. Guha. Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing, 34:803--824, 2005. Google ScholarDigital Library
- M. Chleb'ık and J. Chleb'ıková. The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science, 406(3):207--214, 2008. Google ScholarDigital Library
- S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1:195--207, 1972.Google ScholarCross Ref
- J. Edmonds. Optimum branchings. J. Res. Nat. Bur. Standards, B71:233--240, 1967.Google ScholarCross Ref
- F. Eisenbrand and F. Grandoni. An improved approximation algorithm for virtual private network design. In SODA, pages 928--932, 2005. Google ScholarDigital Library
- F. Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. New approaches for virtual private network designs. SIAM Journal on Computing 37(3): 706--721, 2007. Google ScholarDigital Library
- F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer. Approximating connected facility location problems via random facility sampling and core detouring. In SODA, pages 1174--1183, 2008. Google ScholarDigital Library
- F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer. Connected Facility Location via Random Sampling and Core Detouring. Journal of Computer and System Sciences. To appear. Google ScholarDigital Library
- A. Frank and É. Tardos. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica, 7:49--65, 1987. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32:826--834, 1977.Google ScholarCross Ref
- M. R. Garey and D. S. Johnson. Computers and intractability. W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences. Google ScholarDigital Library
- E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1--29, January 1968.Google ScholarDigital Library
- M. X. Goemans and Y. S. Myung. A catalog of Steiner tree formulations. Networks, 23:19--28, 1993.Google ScholarCross Ref
- M. X. Goemans and D.P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24:296--317, 1995. Google ScholarDigital Library
- F. Grandoni and G. F. Italiano. Improved approximation for single-sink buy-at-bulk. In ISAAC, pages 111--120, 2006. Google ScholarDigital Library
- M. Grötschel, L. Lovasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169--197, 1981.Google ScholarCross Ref
- A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener. Provisioning a virtual private network: a network design problem for multicommodity flow. In STOC, pages 389--398, 2001. Google ScholarDigital Library
- A. Gupta, A. Kumar, M. Pál, and T. Roughgarden. Approximation via cost sharing: simpler and better approximation algorithms for network design. Journal of the ACM, 54(3):11, 2007. Google ScholarDigital Library
- F.K. Hwang, D.S. Richards, and P. Winter. The Steiner tree problem. Monograph in Annals of Discrete Mathematics, 53. Elsevier, Amsterdam, 1992.Google Scholar
- K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. In FOCS, pages 448--457, 1998. Google ScholarDigital Library
- M. Karpinski and A. Zelikovsky. New approximation algorithms for the Steiner tree problems. Journal of Combinatorial Optimization, 1(1):47--65, 1997.Google ScholarCross Ref
- L. G. Khachiyan. A polynomial algorithm for linear programming. Soviet Math. Doklady, 20:191--194, 1979. (Russian original in Doklady Akademiia Nauk SSSR, 244:1093--1096).Google Scholar
- J. Könemann, D. Pritchard, and K. Tan. A partition-based relaxation for Steiner trees. CoRR, abs/0712.3568, 2007.Google Scholar
- B. Korte and J. Vygen. Combinatorial Optimization -- Theory and Algorithms. Springer-Verlag, Second Edition, 2002.Google Scholar
- D. Mölle, S. Richter, and P. Rossmanith. A faster algorithm for the Steiner tree problem. In STACS 2006, pages 561--570, 2006. Google ScholarDigital Library
- T. Polzin and S. V. Daneshmand. On Steiner trees and minimum spanning trees in hypergraphs. Operations Research Letters, 31:12--20, 2003. Google ScholarDigital Library
- H. J. Prömel and A. Steger. A new approximation algorithm for the Steiner tree problem with performance ratio 5/3. Journal of Algorithms, 36:89--101, 2000. Google ScholarDigital Library
- S. Rajagopalan and V. V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree problem. In SODA, pages 742--751, 1999. Google ScholarDigital Library
- R. Rizzi. On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristic. Information Processing Letters, 86(6):335--338, 2003. Google ScholarDigital Library
- G. Robins and A. Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics, 19(1):122--134, 2005. A preliminary version appeared in SODA 2000. Google ScholarDigital Library
- C. Swamy and A. Kumar. Prima-dual algorithms for connected facility location problems. Algorithmica, 40(4):245--269, 2004. Google ScholarDigital Library
- K. Talwar. The single-sink buy-at-bulk LP has constant integrality gap. In IPCO, pages 475--486, 2002. Google ScholarDigital Library
- V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001. Google ScholarDigital Library
- A. Z. Zelikovsky. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9:463--470, 1993.Google Scholar
Index Terms
- An improved LP-based approximation for steiner tree
Recommendations
Steiner Tree Approximation via Iterative Randomized Rounding
The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this ...
Matroids and integrality gaps for hypergraphic steiner tree relaxations
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingUntil recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded ...
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an $O(\log n)$-approximation algorithm for the node-weighted prize-collecting ...
Comments