← 研踪 PaperTrailarXiv:2611.24611 · v1
Inapproximability of Euclidean Steiner Tree
首次提交 2026-11-18 23:31
版本更新 2026-11-18 23:31
雷达观测 2026-11-19 15:04
摘要
We consider the Euclidean Steiner Tree problem of connecting given points in by a shortest network allowing the addition of Steiner points anywhere in the space. Arora [FOCS'96/'97, J. ACM'98] gave a polynomial-time approximation scheme (PTAS) for Euclidean Steiner Tree and TSP in every fixed dimension, and Trevisan [STOC'97, SICOMP'00] proved that Euclidean TSP is APX-hard in dimensions. They left open whether Euclidean Steiner Tree admits a PTAS in high dimension. Our first contribution settles this thirty-year-old question by proving APX-hardness in dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in dimensions. This dimension bound is tight up to a factor of , since Arora's scheme is a PTAS in up to dimensions. In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time and proved matching Gap-ETH lower bounds for Euclidean TSP and Rectilinear Steiner Tree, but left a corresponding lower bound for Euclidean Steiner Tree as an open question. Our second contribution answers this question with a nearly tight lower bound on the dependence on accuracy for Euclidean Steiner Tree. However, given the recent claimed refutations of ETH and hence Gap-ETH by OpenAI and Anthropic, we use the weaker assumption that 3SAT has no truly subexponential-time algorithm, that is, no -time algorithm on formulas of size for any constant (a hypothesis one might call weak ETH). Under this assumption, we prove that no -approximation algorithm runs in time for any such .
作者备注:40 pages, 19 figures. Abstract shortened to comply with arXivs length limit
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 23:31 · 最新观测版本
Inapproximability of Euclidean Steiner Tree
We consider the Euclidean Steiner Tree problem of connecting given points in by a shortest network allowing the addition of Steiner points anywhere in the space. Arora [FOCS'96/'97, J. ACM'98] gave a polynomial-time approximation scheme (PTAS) for Euclidean Steiner Tree and TSP in every fixed dimension, and Trevisan [STOC'97, SICOMP'00] proved that Euclidean TSP is APX-hard in dimensions. They left open whether Euclidean Steiner Tree admits a PTAS in high dimension. Our first contribution settles this thirty-year-old question by proving APX-hardness in dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in dimensions. This dimension bound is tight up to a factor of , since Arora's scheme is a PTAS in up to dimensions. In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time and proved matching Gap-ETH lower bounds for Euclidean TSP and Rectilinear Steiner Tree, but left a corresponding lower bound for Euclidean Steiner Tree as an open question. Our second contribution answers this question with a nearly tight lower bound on the dependence on accuracy for Euclidean Steiner Tree. However, given the recent claimed refutations of ETH and hence Gap-ETH by OpenAI and Anthropic, we use the weaker assumption that 3SAT has no truly subexponential-time algorithm, that is, no -time algorithm on formulas of size for any constant (a hypothesis one might call weak ETH). Under this assumption, we prove that no -approximation algorithm runs in time for any such .
查看此版本解读 →查看此版本原文 ↗