Multi-Level Steiner Trees

Authors Reyan Ahmed, Patrizio Angelini , Faryad Darabi Sahneh , Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov , Richard Spence, Joseph Watkins, Alexander Wolff



PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.15.pdf
  • Filesize: 1.02 MB
  • 14 pages

Document Identifiers

Author Details

Reyan Ahmed
  • University of Arizona, Tucson, United States
Patrizio Angelini
  • Universität Tübingen, Tübingen, Germany
Faryad Darabi Sahneh
  • University of Arizona, Tucson, United
Alon Efrat
  • University of Arizona, Tucson, United States
David Glickenstein
  • University of Arizona, Tucson, United States
Martin Gronemann
  • Universität zu Köln, Cologne, Germany
Niklas Heinsohn
  • Universität Tübingen, Tübingen, Germany
Stephen G. Kobourov
  • University of Arizona, Tucson, United States
Richard Spence
  • University of Arizona, Tucson, United States
Joseph Watkins
  • University of Arizona, Tucson, United States
Alexander Wolff
  • Universität Würzburg, Würzburg, Germany

Cite AsGet BibTex

Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. Multi-Level Steiner Trees. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SEA.2018.15

Abstract

In the classical Steiner tree problem, one is given an undirected, connected graph G=(V,E) with non-negative edge costs and a set of terminals T subseteq V. The objective is to find a minimum-cost edge set E' subseteq E that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of rho = ln(4)+epsilon < 1.39. In this paper, we study a natural generalization, the multi-level Steiner tree (MLST) problem: given a nested sequence of terminals T_1 subset ... subset T_k subseteq V, compute nested edge sets E_1 subseteq ... subseteq E_k subseteq E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under names such as Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two natural heuristics with approximation factor O(k). Based on these, we introduce a composite algorithm that requires 2^k Steiner tree computations. We determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio and needs at most 2k Steiner tree computations. We compare five algorithms experimentally on several classes of graphs using four types of graph generators. We also implemented an integer linear program for MLST to provide ground truth. Our combined algorithm outperforms the others both in theory and in practice when the number of levels is small (k <= 22), which works well for applications such as designing multi-level infrastructure or network visualization.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Routing and network design problems
Keywords
  • Approximation algorithm
  • Steiner tree
  • multi-level graph representation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. Multi-level Steiner trees, 2018. URL: http://arxiv.org/abs/1804.02627.
  2. Sanjeev Arora. Polynomial time approximation schemes for Euclidean Traveling Salesman and other geometric problems. J. ACM, 45(5):753-782, 1998. URL: http://dx.doi.org/10.1145/290179.290180.
  3. Anantaram Balakrishnan, Thomas L. Magnanti, and Prakash Mirchandani. Modeling and heuristic worst-case performance analysis of the two-level network design problem. Management Sci., 40(7):846-867, 1994. URL: http://dx.doi.org/10.1287/mnsc.40.7.846.
  4. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512, 1999. Google Scholar
  5. Marshall Bern and Paul Plassmann. The Steiner problem with edge lengths 1 and 2. Inform. Process. Lett., 32(4):171-176, 1989. URL: http://dx.doi.org/10.1016/0020-0190(89)90039-2.
  6. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1-6:33, 2013. URL: http://dx.doi.org/10.1145/2432622.2432628.
  7. Moses Charikar, Joseph (Seffi) Naor, and Baruch Schieber. Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Trans. Networking, 12(2):340-348, 2004. URL: http://dx.doi.org/10.1109/TNET.2004.826288.
  8. Miroslav Chlebík and Janka Chlebíková. The Steiner tree problem on graphs: Inapproximability results. Theoret. Comput. Sci., 406(3):207-214, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.06.046.
  9. Julia Chuzhoy, Anupam Gupta, Joseph (Seffi) Naor, and Amitabh Sinha. On the approximability of some network design problems. ACM Trans. Algorithms, 4(2):23:1-23:17, 2008. URL: http://dx.doi.org/10.1145/1361192.1361200.
  10. Paul Erdös and Alfréd Rényi. On random graphs I. Publicationes Mathematicae (Debrecen), 6:290-297, 1959. Google Scholar
  11. Edgar N. Gilbert and Henry O. Pollak. Steiner minimal trees. SIAM J. Appl. Math., 16(1):1-29, 1968. URL: http://dx.doi.org/10.1137/0116001.
  12. Mathias Hauptmann and Marek Karpinski (eds.). A compendium on Steiner tree problems, 2015. URL: http://theory.cs.uni-bonn.de/info5/steinerkompendium/.
  13. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. URL: http://dx.doi.org/10.1007/978-1-4684-2001-2_9.
  14. Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, and Alexander Zelikovsky. Improved approximation algorithms for the quality of service multicast tree problem. Algorithmica, 42(2):109-120, 2005. URL: http://dx.doi.org/10.1007/s00453-004-1133-y.
  15. Prakash Mirchandani. The multi-tier tree problem. INFORMS J. Comput., 8(3):202-218, 1996. Google Scholar
  16. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4):1298-1309, 1999. URL: http://dx.doi.org/10.1137/S0097539796309764.
  17. Mark E.J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167-256, 2003. URL: http://dx.doi.org/10.1137/S003614450342480.
  18. Mathew Penrose. Random geometric graphs, volume 5 of Oxford Studies in Probability. Oxford University Press, 2003. Google Scholar
  19. Tobias Polzin and Siavash Vahdati Daneshmand. A comparison of Steiner tree relaxations. Discrete Appl. Math., 112(1):241-261, 2001. URL: http://dx.doi.org/10.1016/S0166-218X(00)00318-8.
  20. Hans Jürgen Prömel and Angelika Steger. The Steiner Tree Problem. Vieweg and Teubner Verlag, 2002. Google Scholar
  21. Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math., 19(1):122-134, 2005. URL: http://dx.doi.org/10.1137/S0895480101393155.
  22. Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ’small-world' networks. Nature, 393(6684):440-442, 1998. URL: http://dx.doi.org/10.1038/30918.
  23. Pawel Winter. Steiner problem in networks: A survey. Networks, 17(2):129-167, 1987. URL: http://dx.doi.org/10.1002/net.3230170203.
  24. Guoliang Xue, Guo-Hui Lin, and Ding-Zhu Du. Grade of service Steiner minimum trees in the Euclidean plane. Algorithmica, 31(4):479-500, 2001. URL: http://dx.doi.org/10.1007/s00453-001-0050-6.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail