NP-hardness and a PTAS for the Euclidean Steiner Line Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915055733309440 |
|---|---|
| author | Bartlmae, Simon Jünger, Paul J. Langetepe, Elmar |
| author_facet | Bartlmae, Simon Jünger, Paul J. Langetepe, Elmar |
| contents | The Euclidean Steiner Tree Problem (EST) seeks a minimum-cost tree interconnecting a given set of terminal points in the Euclidean plane, allowing the use of additional intersection points. In this paper, we consider two variants that include an additional straight line $γ$ with zero cost, which must be incorporated into the tree. In the Euclidean Steiner fixed Line Problem (ESfL), this line is given as input and can be treated as a terminal. In contrast, the Euclidean Steiner Line Problem (ESL) requires determining the optimal location of $γ$. Despite recent advances, including heuristics and a 1.214-approximation algorithm for both problems, a formal proof of NP-hardness has remained open. In this work, we close this gap by proving that both the ESL and ESfL are NP-hard. Additionally, we prove that both problems admit a polynomial-time approximation scheme (PTAS), by demonstrating that approximation algorithms for the EST can be adapted to the ESL and ESfL with appropriate modifications. Specifically, we show ESfL$\leq_{\text{PTAS}}$EST and ESL$\leq_{\text{PTAS}}$EST, i.e., provide a PTAS reduction to the EST. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_07046 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | NP-hardness and a PTAS for the Euclidean Steiner Line Problem Bartlmae, Simon Jünger, Paul J. Langetepe, Elmar Computational Geometry Data Structures and Algorithms The Euclidean Steiner Tree Problem (EST) seeks a minimum-cost tree interconnecting a given set of terminal points in the Euclidean plane, allowing the use of additional intersection points. In this paper, we consider two variants that include an additional straight line $γ$ with zero cost, which must be incorporated into the tree. In the Euclidean Steiner fixed Line Problem (ESfL), this line is given as input and can be treated as a terminal. In contrast, the Euclidean Steiner Line Problem (ESL) requires determining the optimal location of $γ$. Despite recent advances, including heuristics and a 1.214-approximation algorithm for both problems, a formal proof of NP-hardness has remained open. In this work, we close this gap by proving that both the ESL and ESfL are NP-hard. Additionally, we prove that both problems admit a polynomial-time approximation scheme (PTAS), by demonstrating that approximation algorithms for the EST can be adapted to the ESL and ESfL with appropriate modifications. Specifically, we show ESfL$\leq_{\text{PTAS}}$EST and ESL$\leq_{\text{PTAS}}$EST, i.e., provide a PTAS reduction to the EST. |
| title | NP-hardness and a PTAS for the Euclidean Steiner Line Problem |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.07046 |