Computing a minimum-cost \(k\)-hop Steiner tree in tree-like metrics. (English) Zbl 07559389
Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 18, 15 p. (2020).
Summary: We consider the problem of computing a Steiner tree of minimum cost under a \(k\)-hop constraint which requires the depth of the tree to be at most \(k\). Our main result is an exact algorithm for metrics induced by graphs of bounded treewidth that runs in time \(n^{O(k)}\). For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if \(k\) is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the \(k\)-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension.
For the entire collection see [Zbl 1445.68013].
For the entire collection see [Zbl 1445.68013].
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway dimension and provably efficient shortest path algorithms. J. ACM, 63(5):41:1-41:26, 2016. · Zbl 1425.68447 |
| [2] | Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 782-793, 2010. · Zbl 1288.68243 |
| [3] | Laurent Alfandari and Vangelis Th. Paschos. Approximating minimum spanning tree of depth 2. International Transactions in Operational Research, 6(6):607-622, 1999. |
| [4] | Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, and Martin Skutella. Approximating k-hop minimum-spanning trees. Oper. Res. Lett., 33(2):115-120, 2005. · Zbl 1099.90064 |
| [5] | Omer Angel, Abraham D. Flaxman, and David B. Wilson. A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and steiner trees in random networks. Combinatorica, 32(1):1-33, 2012. · Zbl 1299.05288 |
| [6] | Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, and Michiel Smid. Euclidean spanners: Short, thin, and lanky. In Proceedings of the Twenty-Seventh Annual ACM Sympo-sium on Theory of Computing, page 489-498, 1995. · Zbl 0968.68533 |
| [7] | Anantaram Balakrishnan and Kemal Altinkemer. Using a hop-constrained model to generate alternative communication network design. INFORMS Journal on Computing, 4(2):192-205, 1992. · Zbl 0825.90395 |
| [8] | Judit Bar-Ilan, Guy Kortsarz, and David Peleg. Generalized submodular cover problems and applications. Theor. Comput. Sci., 250(1-2):179-200, 2001. · Zbl 0952.68063 |
| [9] | Marshall Bern and Paul Plassmann. The steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4), 1989. · Zbl 0677.68074 |
| [10] | Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. · Zbl 0864.68074 |
| [11] | Paz Carmi, Lilach Chaitman-Yerushalmi, and Ohad Trabelsi. Bounded-hop communication networks. Algorithmica, 80(11):3050-3077, 2018. · Zbl 1410.68366 |
| [12] | Markus Chimani, Petra Mutzel, and Bernd Zey. Improved steiner tree algorithms for bounded treewidth. Journal of Discrete Algorithms, 16:67-78, 2012. · Zbl 1257.05166 |
| [13] | Markus Chimani and Joachim Spoerhase. Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30, pages 238-248, 2015. · Zbl 1355.68204 |
| [14] | Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Treewidth. In Parameterized algorithms, chapter 7, pages 151-244. Springer, Cham, 2015. doi:10.1007/978-3-319-21275-3_7. · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3_7 |
| [15] | Geir Dahl, Luís Gouveia, and Cristina Requejo. On formulations and methods for the hop-constrained minimum spanning tree problem. In Mauricio G. C. Resende and Panos M. · Zbl 1118.90051 |
| [16] | Pardalos, editors, Handbook of Optimization in Telecommunications, pages 493-515. Springer, Boston, MA, 2006. · Zbl 1100.90001 |
| [17] | Michael Elkin and Shay Solomon. Narrow-shallow-low-light trees with and without steiner points. SIAM Journal on Discrete Mathematics, 25(1):181-210, 2011. · Zbl 1227.68082 |
| [18] | Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, and Ian Post. A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM Journal on Computing, 47(4):1667-1704, 2018. · Zbl 1398.68672 |
| [19] | Luis Gouveia. Using the miller-tucker-zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Comput. Oper. Res., 22(9):959-970, 1995. · Zbl 0854.90139 |
| [20] | Luis Gouveia, Luidi Simonetti, and Eduardo Uchoa. Modeling hop-constrained and diameter-constrained minimum spanning tree problems as steiner tree problems over layered graphs. Math. Program., 128(1-2):123-148, 2011. 18:15 · Zbl 1218.90201 |
| [21] | Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228-248, 1999. · Zbl 0928.68137 |
| [22] | Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In FOCS, pages 534-543. IEEE Computer Society, 2003. |
| [23] | Martin Haenggi. Twelve reasons not to route over many short hops. VTC2004-Fall, 5:3130-3134 Vol. 5, 2004. |
| [24] | MohammadTaghi Hajiaghayi, Guy Kortsarz, and Mohammad R. Salavatipour. Approximating buy-at-bulk and shallow-light k-steiner trees. Algorithmica, 53(1):89-103, 2009. · Zbl 1176.68242 |
| [25] | Vojtěch Jarník and Miloš Kössler. O minimálních grafech, obsahujících n daných bodů. Časopis pro pěstování matematiky a fysiky, 63(8):223-235, 1934. · Zbl 0009.13106 |
| [26] | Erez Kantor and David Peleg. Approximate hierarchical facility location and applications to the bounded depth steiner tree and range assignment problems. J. Discrete Algorithms, 7(3):341-362, 2009. · Zbl 1187.68348 |
| [27] | Bernhard Korte and Jaroslav Nešetřil. Vojtěch Jarník’s work in combinatorial optimization. Discrete Mathematics, 235(1-3):1-17, 2001. · Zbl 1024.01018 |
| [28] | Guy Kortsarz and David Peleg. Approximating shallow-light trees. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, page 103-110, 1997. · Zbl 1321.05270 |
| [29] | Sören Laue and Domagoj Matijević. Approximating k-hop minimum spanning trees in euclidean metrics. Inf. Process. Lett., 107(3-4):96-101, 2008. · Zbl 1186.68562 |
| [30] | Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. · Zbl 1281.68236 |
| [31] | Prabhu Manyem and Matthias FM Stallmann. Some approximation results in multicasting. Technical report, North Carolina State University at Raleigh, USA, 1996. |
| [32] | Vikram Raj Saksena. Topological analysis of packet networks. IEEE Journal on Selected Areas in Communications, 7(8):1243-1252, 1989. |
| [33] | Stefan Voß. The steiner tree problem with hop constraints. Annals OR, 86:321-345, 1999. · Zbl 0921.90072 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
