On Steiner Trees of the Regular Simplex
On Steiner Trees of the Regular Simplex
复制标题
DOI：
10.48550/arxiv.2312.01252
复制
发表时间：
2023-12
期刊：
影响因子：
--
通讯作者：
Henry Fleischmann;Q. GuillermoA.Gamboa;S. KarthikC.;Josef Matejka;Jakub Petr
中科院分区：
文献类型：
--
作者：
Henry Fleischmann;Q. GuillermoA.Gamboa;S. KarthikC.;Josef Matejka;Jakub Petr
在欧几里德斯坦纳树问题中，我们在度量空间中输入一组点（称为终端），目标是找到连接它们的最小代价树。空间中的其他点（称为Steiner点）可以作为解中的节点引入。Arora [JACM'98]和Mitchell [SICOMP'99]的开创性工作提供了一种多项式时间近似方案（PTAS），用于解决固定维度的欧氏斯坦纳树问题。然而，这个问题在更高维度中仍然知之甚少（例如当维度在终端数量上是对数时），并且在高维中排除PTAS问题是一个众所周知的长期未决问题（例如，参见Trevisan [SICOMP'00]）。此外，显式构造的最佳斯坦纳树仍然是未知的，几乎所有的研究良好的高维点配置。此外，绝大多数关于（高维）欧几里得斯坦纳树的最先进的结构结果是在20世纪60年代建立的，在半个世纪内没有值得注意的更新。在本文中，我们重新审视高维欧几里德斯坦纳树，证明新的结构结果。我们还建立了一个联系之间的计算硬度的欧氏斯坦纳树问题和理解最佳斯坦纳树的正则单纯形（单纯复形），提出了几个apturtures，并表明，其中一些足以解决的状态的不可逼近的欧氏斯坦纳树问题。出于这种联系，我们研究了正则单形的最优Steiner树，证明了它们的最优Steiner树的新结构性质，重新审视了Smith关于它们的最优拓扑的一个旧猜想，并提供了该拓扑的候选最优Steiner树的第一个明确的一般构造。
In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the $\ell_2$-metric space and the goal is to find the minimum-cost tree connecting them. Additional points (called Steiner points) from the space can be introduced as nodes in the solution. The seminal works of Arora [JACM'98] and Mitchell [SICOMP'99] provide a Polynomial Time Approximation Scheme (PTAS) for solving the Euclidean Steiner Tree problem in fixed dimensions. However, the problem remains poorly understood in higher dimensions (such as when the dimension is logarithmic in the number of terminals) and ruling out a PTAS for the problem in high dimensions is a notoriously long standing open problem (for example, see Trevisan [SICOMP'00]). Moreover, the explicit construction of optimal Steiner trees remains unknown for almost all well-studied high-dimensional point configurations. Furthermore, a vast majority the state-of-the-art structural results on (high-dimensional) Euclidean Steiner trees were established in the 1960s, with no noteworthy update in over half a century. In this paper, we revisit high-dimensional Euclidean Steiner trees, proving new structural results. We also establish a link between the computational hardness of the Euclidean Steiner Tree problem and understanding the optimal Steiner trees of regular simplices (and simplicial complexes), proposing several conjectures and showing that some of them suffice to resolve the status of the inapproximability of the Euclidean Steiner Tree problem. Motivated by this connection, we investigate optimal Steiner trees of regular simplices, proving new structural properties of their optimal Steiner trees, revisiting an old conjecture of Smith [Algorithmica'92] about their optimal topology, and providing the first explicit, general construction of candidate optimal Steiner trees for that topology.