PTAS for geometric hitting set problems via local search

DOI10.1145/1542362.1542367MaRDI QIDQ5370695zbMATH OpenOpenAlexFDO

Authors 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 algorithmepsilon netshitting setslocal search

Mathematics Subject Classification ID

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

Recommendations

• Improved results on geometric hitting set problems
• Improved local search for geometric hitting set
• Limits of local search: quality and efficiency
• Near-linear approximation algorithms for geometric hitting sets
• Near-linear approximation algorithms for geometric hitting sets

Cited in

(26)

• Near-linear time approximation schemes for geometric maximum coverage
• Exact multi-covering problems with geometric sets
• A tight analysis of geometric local search
• A constant-factor approximation algorithm for vertex guarding a WV-polygon
• Minimum vertex cover in ball graphs through local search
• A scheme for computing minimum covers within simple regions
• Near-linear approximation algorithms for geometric hitting sets
• The matroid intersection cover problem
• Improved local search for geometric hitting set
• Unique covering problems with geometric sets
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• A PTAS for the Weighted Unit Disk Cover Problem
• Approximation algorithms for maximum independent set of pseudo-disks
• Guarding 1.5D terrains with demands
• Optimality of geometric local search
• Limits of local search: quality and efficiency
• Algorithms for the line-constrained disk coverage and related problems
• Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
• Algorithms for the line-constrained disk coverage and related problems
• Capacitated discrete unit disk cover
• Local search strikes again: PTAS for variants of geometric covering and packing
• Geometric hitting set for line-constrained disks
• Online hitting set of \(d\)-dimensional fat objects
• PTASs for secure dominating set in planar graphs and growth-bounded graphs
• Algorithms for halfplane coverage and related problems
• Balanced independent and dominating sets on colored interval graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5370695)