PTAS for geometric hitting set problems via local search
From MaRDI portal
Publication:5370695
DOI10.1145/1542362.1542367zbMath1380.68403MaRDI QIDQ5370695
Publication date: 20 October 2017
Published in: Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1542362.1542367
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
Related Items
Guarding 1.5D terrains with demands, Capacitated discrete unit disk cover, Covering uncertain points in a tree, Approximation algorithms for maximum independent set of pseudo-disks, Near-linear time approximation schemes for geometric maximum coverage, Minimum vertex cover in ball graphs through local search, Approximation algorithms for the connected sensor cover problem, A scheme for computing minimum covers within simple regions, Near-linear approximation algorithms for geometric hitting sets, Unique Covering Problems with Geometric Sets, Linear Time Approximation Schemes for Geometric Maximum Coverage, A PTAS for the Weighted Unit Disk Cover Problem