Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem

Authors Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, Richard Spence



PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.4.pdf
  • Filesize: 1.64 MB
  • 21 pages

Document Identifiers

Author Details

Reyan Ahmed
  • University of Arizona, Tucson, AZ, USA
Faryad Darabi Sahneh
  • University of Arizona, Tucson, AZ, USA
Keaton Hamm
  • University of Texas at Arlington, Arlington, TX, USA
Stephen Kobourov
  • University of Arizona, Tucson, AZ, USA
Richard Spence
  • University of Arizona, Tucson, AZ, USA

Cite AsGet BibTex

Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence. Kruskal-Based Approximation Algorithm for the Multi-Level Steiner Tree Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.4

Abstract

We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln |T|+1), 𝓁 ρ}-approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and 𝓁 is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ≈1.39, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • multi-level
  • Steiner tree
  • approximation algorithms

Metrics

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

References

  1. Abu Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. Multi-level Steiner trees. In 17th International Symposium on Experimental Algorithms, (SEA), pages 15:1-15:14, 2018. URL: https://doi.org/10.4230/LIPIcs.SEA.2018.15.
  2. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512, 1999. Google Scholar
  3. 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: https://doi.org/10.1145/2432622.2432628.
  4. M. Charikar, J. Naor, and B. Schieber. Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Transactions on Networking, 12(2):340-348, April 2004. URL: https://doi.org/10.1109/TNET.2004.826288.
  5. Miroslav Chlebík and Janka Chlebíková. The Steiner tree problem on graphs: Inapproximability results. Theoret. Comput. Sci., 406(3):207-214, 2008. URL: https://doi.org/10.1016/j.tcs.2008.06.046.
  6. 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: https://doi.org/10.1145/1361192.1361200.
  7. Marcus Poggi de Aragão and Renato F Werneck. On the implementation of mst-based heuristics for the Steiner problem in graphs. In Workshop on algorithm engineering and experimentation, pages 1-15. Springer, 2002. Google Scholar
  8. Paul Erdös and Alfréd Rényi. On random graphs, i. Publicationes Mathematicae (Debrecen), 6:290-297, 1959. Google Scholar
  9. Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369-384, 1991. URL: https://doi.org/10.1137/0404033.
  10. 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: https://doi.org/10.1007/s00453-004-1133-y.
  11. T. Koch, A. Martin, and S. Voß. SteinLib: An updated library on Steiner tree problems in graphs. Technical Report ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, Berlin, 2000. URL: http://elib.zib.de/steinlib.
  12. Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math., 19(1):122-134, 2005. URL: https://doi.org/10.1137/S0895480101393155.
  13. H. Takahashi and A. Matsuyama. An approximate solution for Steiner problem in graphs. Math. Japonica, 24(6):573-577, 1980. Google Scholar
  14. SM Wang. A multiple source algorithm for suboptimum Steiner trees in graphs. In Proc. International Workshop on Graphtheoretic Concepts in Computer Science (H. Noltemeier, ed.), Trauner, W urzburg, pages 387-396, 1985. Google Scholar
  15. Duncan J Watts and Steven H Strogatz. Collective dynamics of ‘small-world’networks. nature, 393(6684):440, 1998. Google Scholar
  16. Peter Widmayer. On approximation algorithms for Steiner’s problem in graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 17-28. Springer, 1986. Google Scholar
  17. Y.F. Wu, P. Widmayer, and C.K. Wong. A faster approximation algorithm for the Steiner problem in graphs. Acta Inform., 23(2):223–229, 1986. Google Scholar
  18. 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: https://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