Improved local search for geometric hitting set

DOI10.4230/LIPICS.STACS.2015.184MaRDI QIDQ2954994zbMATH OpenFDO

Authors Norbert Bus, Shashwat Garg, Nabil H. Mustafa, Saurabh Ray

Publication date 24 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2015.184

zbMATH Keywords

Delaunay triangulationdisksgeometric algorithmshitting setslocal search

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Limits of local search: quality and efficiency
• PTAS for geometric hitting set problems via local search
• Optimality of geometric local search
• Improved results on geometric hitting set problems
• A tight analysis of geometric local search

Cited in

(12)

• A tight analysis of geometric local search
• Simple PTAS's for families of graphs excluding a minor
• Tighter estimates for -nets for disks
• Geometric hitting sets for disks: theory and practice
• Constant-factor approximation for TSP with disks
• Discrete unit square cover problem
• Optimality of geometric local search
• Limits of local search: quality and efficiency
• PTAS for geometric hitting set problems via local search
• Improved results on geometric hitting set problems
• Geometric covering via extraction theorem
• Approximation and parameterized algorithms for covering with disks of two types of radii

This page was built for publication: Improved local search for geometric hitting set

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