On Approximability of Steiner Tree in $\ell_p$-metrics
Open Access
- 20 January 2025
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Abstract
In the Continuous Steiner Tree problem (CST), we are given as input a set of points (called terminals) in a metric space and ask for the minimum-cost tree connecting them. Additional points (called Steiner points) from the metric space can be introduced as nodes in the solution. In the Discrete Steiner Tree problem (DST), we are given in addition to the terminals, a set of facilities, and any solution tree connecting the terminals can only contain the Steiner points from this set of facilities. Trevisan [SICOMP'00] showed that CST and DST are APX-hard when the input lies in the $\ell_1$-metric (and Hamming metric). Chleb\'ik and Chleb\'ikov\'a [TCS'08] showed that DST is NP-hard to approximate to factor of $96/95\approx 1.01$ in the graph metric (and consequently $\ell_\infty$-metric). Prior to this work, it was unclear if CST and DST are APX-hard in essentially every other popular metric. In this work, we prove that DST is APX-hard in every $\ell_p$-metric. We also prove that CST is APX-hard in the $\ell_{\infty}$-metric. Finally, we relate CST and DST, showing a general reduction from CST to DST in $\ell_p$-metrics.Comment: Abstract shortened. Journal version for TheoretiCS
Keywords
All Related Versions
This publication has 57 references indexed in Scilit:
- Solving Steiner trees: Recent advances, challenges, and perspectivesNetworks, 2020
- Handbook of Optimization in Telecommunications2006
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Steiner Tree Problems in VLSI Layout Designs2001
- Steiner Trees in Industry2001
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3Journal of Algorithms, 2000
- On the Asymptotic Behaviour of Some Towers of Function Fields over Finite FieldsJournal of Number Theory, 1996
- Disproofs of Generalized Gilbert–Pollak Conjecture on the Steiner Ratio in Three or More DimensionsJournal of Combinatorial Theory, Series A, 1996
- Steiner tree problemsNetworks, 1992