On Approximability of Steiner Tree in $\ell_p$-metrics
Authors:
- Karthik C. S.KSKarthik C. S.
Preprint
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. As an immediate consequence, this yields a $1.39$-approximation polynomial time algorithm for CST in $\ell_p$-metrics.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Solving Steiner trees: Recent advances, challenges, and perspectivesNetworks, 2020
- On the history of the Euclidean Steiner tree problemArchive for History of Exact Sciences, 2013
- Steiner Trees in Industry2006
- 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
- 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
- The hardness of approximation: Gap locationcomputational complexity, 1994
- An 11/6-approximation algorithm for the network steiner problemAlgorithmica, 1993
- Combinatorial Algorithms for Integrated Circuit Layout1990