2026-08-03T22:52:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12185 2024-03-06T10:49:39Z ddc:004 open_access

Faster Approximation Algorithms for Geometric Set Cover Chan, Timothy M. He, Qizheng Set cover approximation algorithms multiplicate weight update method random sampling shallow cuttings 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Qizheng He 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.27 urn:nbn:de:0030-drops-121856 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.27 eng https://creativecommons.org/licenses/by/3.0/legalcode