Improved approximation algorithms for geometric set cover

DOI10.1145/1064092.1064115zbMath1379.68347OpenAlexW2122585291MaRDI QIDQ5370605

Kenneth L. Clarkson, Kasturi R. Varadarajan

Publication date: 20 October 2017

Published in: Proceedings of the twenty-first annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1064092.1064115

zbMATH Keywords

algorithmsapproximationset cover

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (9)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ Approximate guarding of monotone and rectilinear polygons ⋮ Covering Points by Unit Disks of Fixed Location ⋮ Polynomial-time approximation schemes for piercing and covering with applications in wireless networks ⋮ On guarding the vertices of rectilinear domains ⋮ Exact and approximation algorithms for geometric and capacitated set cover problems ⋮ Improved approximations for guarding 1.5-dimensional terrains ⋮ Parametric search: three new applications ⋮ Unnamed Item

This page was built for publication: Improved approximation algorithms for geometric set cover