论文标题
几何套盖的更快近似算法
Faster Approximation Algorithms for Geometric Set Cover
论文作者
论文摘要
我们将$ O（1）$ - 近似算法的运行时间提高了几何设置中的设定覆盖问题，特别是在平面中的磁盘覆盖点，或在三个维度中覆盖一个半空间的覆盖点。在未加权的情况下，Agarwal和Pan [SOCG 2014]通过使用多种重量更新（MWU）方法的变体结合几何数据结构的变体，给出了随机的$ O（N \ log^4 n）$ - 时间，$ O（1）$ - 近似算法。我们简化了其中一种方法的数据结构要求，并获得确定性的$ o（n \ log^3 n \ log \ log \ log n）$ - 时间算法。有了进一步的新想法，我们获得了更快的随机$ o（n \ log n（\ log \ log \ log n）^{o（1）}）$ - 时间算法。 对于加权问题，我们还通过简单修改MWU方法和准统一的采样技术，给出一个随机$ O（n \ log^4n \ log \ log \ log n）$ - 时间，$ O（1）$ - 近似算法。
We improve the running times of $O(1)$-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized $O(n\log^4 n)$-time, $O(1)$-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic $O(n\log^3 n\log\log n)$-time algorithm. With further new ideas, we obtain a still faster randomized $O(n\log n(\log\log n)^{O(1)})$-time algorithm. For the weighted problem, we also give a randomized $O(n\log^4n\log\log n)$-time, $O(1)$-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.
