skip to main content
research-article

Steiner Tree Approximation via Iterative Randomized Rounding

Published: 01 February 2013 Publication History

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.

References

[1]
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.
[2]
Alon, N. and Spencer, J. 2008. The Probabilistic Method. Wiley.
[3]
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.
[4]
Arora, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5, 753--782.
[5]
Arora, S. and Barak, B. 2009. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge.
[6]
Bern, M. and Plassmann, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 4, 171--176.
[7]
Borchers, A. and Du, D. 1997. The k-Steiner ratio in graphs. SIAM J. Comput. 26, 3, 857--869.
[8]
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.
[9]
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.
[10]
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.
[11]
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.
[12]
Charikar, M. and Guha, S. 2005. Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 803--824.
[13]
Chlebík, M. and Chlebíková, J. 2008. The Steiner tree problem on graphs: Inapproximability results. Theoret. Comput. Sci. 406, 3, 207--214.
[14]
Dreyfus, S. E. and Wagner, R. A. 1972. The Steiner problem in graphs. Networks 1, 195--207.
[15]
Edmonds, J. 1967. Optimum branchings. J. Res. Nat. Bureau Stand. B71, 233--240.
[16]
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.
[17]
Eisenbrand, F., Grandoni, F., Oriolo, G., and Skutella, M. 2007. New approaches for virtual private network design. SIAM J. Comput. 37, 3, 706--721.
[18]
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.
[19]
Frank, A. and Tardos, É. 1987. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49--65.
[20]
Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability. W. H. Freeman and Co.
[21]
Gilbert, E. N. and Pollak, H. O. 1968. Steiner minimal trees. SIAM J. Appl. Math. 16, 1, 1--29.
[22]
Goemans, M. X. and Myung, Y. 1993. A catalog of Steiner tree formulations. Networks 23, 1, 19--28.
[23]
Goemans, M. X. and Williamson, D. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296--317.
[24]
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.
[25]
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.
[26]
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.
[27]
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.
[28]
Grötschel, M., Lovasz, L., and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169--197.
[29]
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.
[30]
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.
[31]
Hwang, F., Richards, D., and Winter, P. 1992. The Steiner Tree Problem. Monograph in Annals of Discrete Mathematics, 53. Elsevier.
[32]
Jain, K. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 1, 39--60.
[33]
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.
[34]
Karpinski, M. and Zelikovsky, A. 1997. New approximation algorithms for the Steiner tree problem. J. Combinat. Optim. 1, 1, 47--65.
[35]
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).
[36]
Könemann, J., Pritchard, D., and Tan, K. 2011. A partition-based relaxation for Steiner trees. Math. Prog. 127, 2, 345--370.
[37]
Mitzenmacher, M. and Upfal, E. 2005. Probability and Computing. Cambridge University Press, Cambridge. Randomized algorithms and probabilistic analysis.
[38]
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.
[39]
Niven, I., Zuckerman, H. S., and Montgomery, H. L. 1991. An Introduction to the Theory of Numbers. John Wiley & Sons Inc.
[40]
Polzin, T. and Vahdati-Daneshmand, S. 2003. On Steiner trees and minimum spanning trees in hypergraphs. Oper. Res. Lett. 31, 1, 12--20.
[41]
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.
[42]
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.
[43]
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.
[44]
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.
[45]
Robins, G. and Zelikovsky, A. 2005. Tighter bounds for graph Steiner tree approximation. SIAM J. Disc. Math. 19, 1, 122--134.
[46]
Swamy, C. and Kumar, A. 2004. Primal-dual algorithms for connected facility location problems. Algorithmica 40, 4, 245--269.
[47]
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.
[48]
Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag.
[49]
Zelikovsky, A. 1993. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463--470.

Cited By

View all
  • (2025)The parameterized complexity of the survivable network design problemJournal of Computer and System Sciences10.1016/j.jcss.2024.103604148(103604)Online publication date: Mar-2025
  • (2025)Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraintsDiscrete Applied Mathematics10.1016/j.dam.2024.10.014361(258-275)Online publication date: Jan-2025
  • (2024)Online Generalized Network Design Under (Dis)Economies of ScaleMathematics of Operations Research10.1287/moor.2022.134949:1(107-124)Online publication date: 1-Feb-2024
  • Show More Cited By

Index Terms

  1. Steiner Tree Approximation via Iterative Randomized Rounding

    Recommendations

    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

    Information & Contributors

    Information

    Published In

    cover image Journal of the ACM
    Journal of the ACM  Volume 60, Issue 1
    February 2013
    149 pages
    ISSN:0004-5411
    EISSN:1557-735X
    DOI:10.1145/2432622
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 February 2013
    Accepted: 01 November 2012
    Revised: 01 November 2012
    Received: 01 October 2010
    Published in JACM Volume 60, Issue 1

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Approximation algorithms
    2. linear programming relaxations
    3. network design
    4. randomized algorithms

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Funding Sources

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)97
    • Downloads (Last 6 weeks)8
    Reflects downloads up to 16 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)The parameterized complexity of the survivable network design problemJournal of Computer and System Sciences10.1016/j.jcss.2024.103604148(103604)Online publication date: Mar-2025
    • (2025)Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraintsDiscrete Applied Mathematics10.1016/j.dam.2024.10.014361(258-275)Online publication date: Jan-2025
    • (2024)Online Generalized Network Design Under (Dis)Economies of ScaleMathematics of Operations Research10.1287/moor.2022.134949:1(107-124)Online publication date: 1-Feb-2024
    • (2024)Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient RoutingSIAM Journal on Computing10.1137/20M136064553:3(588-623)Online publication date: 20-May-2024
    • (2024)Research on multicast routing algorithmsThird International Conference on Electronic Information Engineering and Data Processing (EIEDP 2024)10.1117/12.3032880(82)Online publication date: 5-Jul-2024
    • (2024)The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller Than 22024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00052(730-753)Online publication date: 27-Oct-2024
    • (2024)A (1/2+1/60)—Approximation algorithm for Maximum Weight Series-Parallel SubgraphDiscrete Applied Mathematics10.1016/j.dam.2023.09.019354:C(241-261)Online publication date: 15-Sep-2024
    • (2024)On Rooted k-Connectivity Problems in Quasi-Bipartite DigraphsOperations Research Forum10.1007/s43069-023-00285-65:1Online publication date: 17-Jan-2024
    • (2024)New Algorithms for Steiner Tree ReoptimizationAlgorithmica10.1007/s00453-024-01243-286:8(2652-2675)Online publication date: 1-Aug-2024
    • (2024)Approximation algorithms for node and element connectivity augmentation problemsTheory of Computing Systems10.1007/s00224-024-10175-x68:5(1468-1485)Online publication date: 2-Oct-2024
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media