EUVIMEDEUVIMED entdecken
Crossref

On Approximability of Steiner Tree in $\ell_p$-metrics

Henry Fleischmann, Surya Teja Gavva, Karthik C. S

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →