























For any $ε>0$, Laue and Matijević [CCCG'07, IPL'08] give a PTAS for finding a $(1+ε)$-approximate solution to the $k$-hop MST problem in the Euclidean plane that runs in time $(n/ε)^{O(k/ε)}$. In this paper, we present an algorithm that runs in time $(n/ε)^{O(\log k \cdot(1/ε)^2\cdot\log^2(1/ε))}$. This gives an improvement on the dependency on $k$ on the exponent, while having a worse dependency on $ε$. As in Laue and Matijević, we follow the framework introduced by Arora for Euclidean TSP. Our key ingredients include exponential distance scaling and compression of dynamic programming state tables.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。