License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.27
URN: urn:nbn:de:0030-drops-121856
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12185/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M. ; He, Qizheng

Faster Approximation Algorithms for Geometric Set Cover

pdf-format:
LIPIcs-SoCG-2020-27.pdf (0.5 MB)

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 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.

BibTeX - Entry

@InProceedings{chan_et_al:LIPIcs:2020:12185,
  author =	{Timothy M. Chan and Qizheng He},
  title =	{{Faster Approximation Algorithms for Geometric Set Cover}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12185},
  URN =		{urn:nbn:de:0030-drops-121856},
  doi =		{10.4230/LIPIcs.SoCG.2020.27},
  annote =	{Keywords: Set cover, approximation algorithms, multiplicate weight update method, random sampling, shallow cuttings}
}

Keywords: Set cover, approximation algorithms, multiplicate weight update method, random sampling, shallow cuttings
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI