Jarosław 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 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999].
In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + ε < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence.
As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.
- Agrawal, A., Klein, P., and Ravi, R. 1995. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24, 440--456. Google Scholar
Digital Library
- Alon, N. and Spencer, J. 2008. The Probabilistic Method. Wiley.Google Scholar
- Archer, A., Bateni, M., Hajiaghayi, M., and Karloff, H. 2011. Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput., 40, 2, 309--332. Google ScholarDigital Library
- Arora, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5, 753--782. Google ScholarDigital Library
- Arora, S. and Barak, B. 2009. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge. Google ScholarDigital Library
- Bern, M. and Plassmann, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 4, 171--176. Google ScholarDigital Library
- Borchers, A. and Du, D. 1997. The k-Steiner ratio in graphs. SIAM J. Comput. 26, 3, 857--869. Google ScholarDigital Library
- Borradaile, G., Klein, P., and Mathieu, C. 2009. An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algor. 5, 3. Google ScholarDigital Library
- Chakrabarty, D., Devanur, N. R., and Vazirani, V. V. 2008. New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 344--358. Google ScholarDigital Library
- Chakrabarty, D., Könemann, J., and Pritchard, D. 2010a. Hypergraphic LP relaxations for Steiner trees. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 383--396. Google ScholarDigital Library
- Chakrabarty, D., Könemann, J., and Pritchard, D. 2010b. Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound. Oper. Res. Lett. 38, 6, 567--570. Google ScholarDigital Library
- Charikar, M. and Guha, S. 2005. Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 803--824. Google ScholarDigital Library
- Chlebík, M. and Chlebíková, J. 2008. The Steiner tree problem on graphs: Inapproximability results. Theoret. Comput. Sci. 406, 3, 207--214. Google ScholarDigital Library
- Dreyfus, S. E. and Wagner, R. A. 1972. The Steiner problem in graphs. Networks 1, 195--207.Google ScholarCross Ref
- Edmonds, J. 1967. Optimum branchings. J. Res. Nat. Bureau Stand. B71, 233--240.Google ScholarCross Ref
- Eisenbrand, F. and Grandoni, F. 2005. An improved approximation algorithm for virtual private network design. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 928--932. Google ScholarDigital Library
- Eisenbrand, F., Grandoni, F., Oriolo, G., and Skutella, M. 2007. New approaches for virtual private network design. SIAM J. Comput. 37, 3, 706--721. Google ScholarDigital Library
- Eisenbrand, F., Grandoni, F., Rothvoss, T., and Schäfer, G. 2010. Connected facility location via random facility sampling and core detouring. J. Comput. Syst. Sci. 76, 8, 709--726. Google ScholarDigital Library
- Frank, A. and Tardos, É. 1987. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49--65. Google ScholarDigital Library
- Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability. W. H. Freeman and Co.Google Scholar
- Gilbert, E. N. and Pollak, H. O. 1968. Steiner minimal trees. SIAM J. Appl. Math. 16, 1, 1--29.Google ScholarDigital Library
- Goemans, M. X. and Myung, Y. 1993. A catalog of Steiner tree formulations. Networks 23, 1, 19--28.Google ScholarCross Ref
- Goemans, M. X. and Williamson, D. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296--317. Google ScholarDigital Library
- Grandoni, F. and Italiano, G. F. 2006. Improved approximation for single-sink buy-at-bulk. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 111--120. Google ScholarDigital Library
- Grandoni, F. and Rothvoss, T. 2011. Approximation algorithms for single and multi-commodity connected facility location. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 248--260. Google ScholarDigital Library
- Grandoni, F., Rothvoss, T., and Sanità, L. 2011. From uncertainty to nonlinearity: Solving virtual private network via single-sink buy-at-bulk. Math. Oper. Res. 36, 2, 185--204. Google ScholarDigital Library
- Gröpl, C., Hougardy, S., Nierhoff, T., and Prömel, H.-J. 2002. Steiner trees in uniformly quasi-bipartite graphs. Inf. Proc. Let. 83, 4, 195--200. Google ScholarDigital Library
- Grötschel, M., Lovasz, L., and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169--197.Google ScholarCross Ref
- Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., and Yener, B. 2001. Provisioning a virtual private network: A network design problem for multicommodity flow. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 389--398. Google ScholarDigital Library
- Gupta, A., Kumar, A., Pál, M., and Roughgarden, T. 2007. Approximation via cost sharing: Simpler and better approximation algorithms for network design. J. ACM 54, 3, 11. Google ScholarDigital Library
- Hwang, F., Richards, D., and Winter, P. 1992. The Steiner Tree Problem. Monograph in Annals of Discrete Mathematics, 53. Elsevier.Google Scholar
- Jain, K. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 1, 39--60.Google ScholarCross Ref
- Jothi, R. and Raghavachari, B. 2009. Improved approximation algorithms for the single-sink buy-at-bulk network design problems. J. Discr. Algor. 7, 2, 249--255. Google ScholarDigital Library
- Karpinski, M. and Zelikovsky, A. 1997. New approximation algorithms for the Steiner tree problem. J. Combinat. Optim. 1, 1, 47--65.Google ScholarCross Ref
- Khachiyan, L. G. 1979. A polynomial algorithm for linear programming. Sov. Math. - Dokl. 20, 191--194. (Russian original in Doklady Akademiia Nauk SSSR, 244:1093--1096).Google Scholar
- Könemann, J., Pritchard, D., and Tan, K. 2011. A partition-based relaxation for Steiner trees. Math. Prog. 127, 2, 345--370.Google ScholarDigital Library
- Mitzenmacher, M. and Upfal, E. 2005. Probability and Computing. Cambridge University Press, Cambridge. Randomized algorithms and probabilistic analysis. Google ScholarDigital Library
- Mölle, D., Richter, S., and Rossmanith, P. 2006. A faster algorithm for the Steiner tree problem. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 561--570. Google ScholarDigital Library
- Niven, I., Zuckerman, H. S., and Montgomery, H. L. 1991. An Introduction to the Theory of Numbers. John Wiley & Sons Inc.Google Scholar
- Polzin, T. and Vahdati-Daneshmand, S. 2003. On Steiner trees and minimum spanning trees in hypergraphs. Oper. Res. Lett. 31, 1, 12--20. Google ScholarDigital Library
- Prömel, H. J. and Steger, A. 2000. A new approximation algorithm for the Steiner tree problem with performance ratio 5/3. J. Algo. 36, 89--101. Google ScholarDigital Library
- Rajagopalan, S. and Vazirani, V. V. 1999. On the bidirected cut relaxation for the metric Steiner tree problem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 742--751. Google ScholarDigital Library
- Rizzi, R. 2003. On Rajagopalan and Vazirani’s 3/2-approximation bound for the Iterated 1-Steiner heuristic. Inf. Proc. Lett. 86, 6, 335--338. Google ScholarDigital Library
- Robins, G. and Zelikovsky, A. 2000. Improved Steiner tree approximation in graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 770--779. Google ScholarDigital Library
- Robins, G. and Zelikovsky, A. 2005. Tighter bounds for graph Steiner tree approximation. SIAM J. Disc. Math. 19, 1, 122--134. Google ScholarDigital Library
- Swamy, C. and Kumar, A. 2004. Primal-dual algorithms for connected facility location problems. Algorithmica 40, 4, 245--269. Google ScholarDigital Library
- Talwar, K. 2002. The single-sink buy-at-bulk LP has constant integrality gap. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 475--486. Google ScholarDigital Library
- Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag. Google ScholarDigital Library
- Zelikovsky, A. 1993. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463--470.Google ScholarCross Ref
Index Terms
- Steiner Tree Approximation via Iterative Randomized Rounding
Recommendations
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 ...
An improved LP-based approximation for steiner tree
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingThe 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 ...
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 ...
Reviews
Krishnaiyan Thulasiraman
The Steiner tree problem is an important combinatorial optimization problem with applications in a wide range of areas, such as very-large-scale integration (VLSI) physical design, the design of virtual private networks, and so on. It is an NP-hard problem and so there has been a good deal of effort to design approximation schemes for it. Of these, the combinatorial algorithm by Robins and Zelikovsky [1] is the best, giving an approximation ratio of 1.55. The aim of this paper is to give “an LP-based approximation algorithm ... with an improved approximation” ratio, namely, ln(4)+ ε < 1.39 for any ε. Toward this goal, the paper first presents an LP-relaxation called DCR and a (1+ ε) approximate solution. This approximate algorithm is then combined in an iterative randomized rounding technique. Using a lemma called the bridge lemma, it is shown that the expected approximation ratio of this randomized algorithm is ln(4) + ε for any ε. It is shown how to derandomize this result using the method of limited independence. This leads to a deterministic approximation algorithm with approximation ratio ln(4) + ε. A byproduct of the analysis in this paper is that the integrality gap of the DCR LP is at most 1.55. This answers in the affirmative “a long standing open problem ... whether there is an LP relaxation of [the] Steiner tree [problem] with [an] integrality gap smaller than 2.” Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments