跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24611 · v1

Inapproximability of Euclidean Steiner Tree

首次提交 2026-11-18 23:31
版本更新 2026-11-18 23:31
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

We consider the Euclidean Steiner Tree problem of connecting nn given points in Rd\mathbb{R}^d 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 O(log⁡n)O(\log n) 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 O(log⁡n)O(\log n) dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP ⊈\not\subseteq SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in O(log⁡log⁡n)O(\log\log n) dimensions. This dimension bound is tight up to a factor of O(log⁡log⁡log⁡n)O(\log\log\log n), since Arora's scheme is a PTAS in up to log⁡log⁡n/log⁡log⁡log⁡n\log\log n/\log\log\log n dimensions. In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time 2Od(ε−(d−1))nlog⁡n2^{O_d(\varepsilon^{-(d-1)})}n\log n 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 2nγ2^{n^γ}-time algorithm on formulas of size nn for any constant γ<1γ<1 (a hypothesis one might call weak ETH). Under this assumption, we prove that no (1+ε)(1+\varepsilon)-approximation algorithm runs in time 2O(ε−γ(d−1))poly(n)2^{O(\varepsilon^{-γ(d-1)})} poly(n) for any such γγ.

作者备注:40 pages, 19 figures. Abstract shortened to comply with arXivs length limit

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-18 23:31 · 最新观测版本

Inapproximability of Euclidean Steiner Tree

We consider the Euclidean Steiner Tree problem of connecting nn given points in Rd\mathbb{R}^d 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 O(log⁡n)O(\log n) 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 O(log⁡n)O(\log n) dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP ⊈\not\subseteq SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in O(log⁡log⁡n)O(\log\log n) dimensions. This dimension bound is tight up to a factor of O(log⁡log⁡log⁡n)O(\log\log\log n), since Arora's scheme is a PTAS in up to log⁡log⁡n/log⁡log⁡log⁡n\log\log n/\log\log\log n dimensions. In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time 2Od(ε−(d−1))nlog⁡n2^{O_d(\varepsilon^{-(d-1)})}n\log n 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 2nγ2^{n^γ}-time algorithm on formulas of size nn for any constant γ<1γ<1 (a hypothesis one might call weak ETH). Under this assumption, we prove that no (1+ε)(1+\varepsilon)-approximation algorithm runs in time 2O(ε−γ(d−1))poly(n)2^{O(\varepsilon^{-γ(d-1)})} poly(n) for any such γγ.

查看此版本解读 →查看此版本原文 ↗