Faster approximation algorithms for geometric set cover

Timothy M. Chan, Qizheng He

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 log4 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 log3 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 log4 n log log n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.

Original languageEnglish (US)
Title of host publication36th International Symposium on Computational Geometry, SoCG 2020
EditorsSergio Cabello, Danny Z. Chen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771436
DOIs
StatePublished - Jun 1 2020
Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
Duration: Jun 23 2020Jun 26 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume164
ISSN (Print)1868-8969

Conference

Conference36th International Symposium on Computational Geometry, SoCG 2020
CountrySwitzerland
CityZurich
Period6/23/206/26/20

Keywords

  • Approximation algorithms
  • Multiplicate weight update method
  • Random sampling
  • Set cover
  • Shallow cuttings

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Faster approximation algorithms for geometric set cover'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M., & He, Q. (2020). Faster approximation algorithms for geometric set cover. In S. Cabello, & D. Z. Chen (Eds.), 36th International Symposium on Computational Geometry, SoCG 2020 [LIPIcs-SoCG-2020-27] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 164). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2020.27