Practical and efficient algorithms for the geometric hitting set problem

DOI10.1016/j.dam.2017.12.018zbMath1396.90072OpenAlexW2790728436MaRDI QIDQ1707909

Saurabh Ray, Nabil H. Mustafa, Norbert Bus

Publication date: 4 April 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.12.018

zbMATH Keywords

computational geometryapproximation algorithmsgeometric hitting sets

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

An approximation algorithm for submodular hitting set problem with linear penalties ⋮ Geometric hitting set for line-constrained disks ⋮ Experiments with unit disk cover algorithms for covering massive pointsets

Uses Software

• CGAL
• SCIP
• SoPlex

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tighter estimates for \(\epsilon\)-nets for disks
• Approximation algorithms for maximum independent set of pseudo-disks
• Improved results on geometric hitting set problems
• SCIP: solving constraint integer programs
• Hitting sets when the VC-dimension is small
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Almost optimal set covers in finite VC-dimension
• Independent set of intersection graphs of convex objects in 2D
• New existence proofs ε-nets
• Fast approximation algorithms for a nonconvex covering problem
• Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Reducibility among Combinatorial Problems