文章基本信息

标题：Faster Approximation Algorithms for Geometric Set Cover
本地全文：下载
作者：Timothy M. Chan ; Qizheng He
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：27:1-27:14
DOI：10.4230/LIPIcs.SoCG.2020.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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â´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Â³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â´n log log n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.
关键词：Set cover; approximation algorithms; multiplicate weight update method; random sampling; shallow cuttings