On Approximability of Steiner Tree in $\ell_p$-metrics
TheoretiCS · 20.01.2025 · Volume 4
DOI: 10.46298/theoretics.25.4 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, online erschienen am 20.01.2025. Verfasst von Henry Fleischmann und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref).
Abstract (Originalsprache)
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
Zitieren
APA
Fleischmann, H., Gavva, S. T., & S, K. C. (2025). On Approximability of Steiner Tree in $\ell_p$-metrics. TheoretiCS, Volume 4. https://doi.org/10.46298/theoretics.25.4
Vancouver
Fleischmann H, Gavva ST, S KC. On Approximability of Steiner Tree in $\ell_p$-metrics. TheoretiCS. 2025;Volume 4. doi:10.46298/theoretics.25.4
BibTeX
@article{Fleischmann2025,
author = {Fleischmann, Henry and Gavva, Surya Teja and S, Karthik C.},
title = {On Approximability of Steiner Tree in $\ell_p$-metrics},
journal = {TheoretiCS},
year = {2025},
volume = {Volume 4},
doi = {10.46298/theoretics.25.4}
}
EUVIMED