PTAS for geometric hitting set problems via local search

DOI10.1145/1542362.1542367zbMath1380.68403OpenAlexW2054505111MaRDI QIDQ5370695

Nabil H. Mustafa, Saurabh Ray

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

zbMATH Keywords

approximation algorithmlocal searchepsilon netshitting sets

Mathematics Subject Classification ID

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

Related Items (20)

Balanced independent and dominating sets on colored interval graphs ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Unique Covering Problems with Geometric Sets ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ The matroid intersection cover problem ⋮ Geometric hitting set for line-constrained disks ⋮ A scheme for computing minimum covers within simple regions ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Guarding 1.5D terrains with demands ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Minimum vertex cover in ball graphs through local search ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Capacitated discrete unit disk cover ⋮ Covering uncertain points in a tree ⋮ Exact multi-covering problems with geometric sets ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon

This page was built for publication: PTAS for geometric hitting set problems via local search