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

Original language | English (US) |
---|---|

Title of host publication | 36th International Symposium on Computational Geometry, SoCG 2020 |

Editors | Sergio Cabello, Danny Z. Chen |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771436 |

DOIs | |

State | Published - Jun 1 2020 |

Event | 36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland Duration: Jun 23 2020 → Jun 26 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 164 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 36th International Symposium on Computational Geometry, SoCG 2020 |
---|---|

Country | Switzerland |

City | Zurich |

Period | 6/23/20 → 6/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

*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