Practical and efficient algorithms for the geometric hitting set problem

DOI10.1016/J.DAM.2017.12.018MaRDI QIDQ1707909zbMATH OpenOpenAlexFDO

Authors Norbert Bus, Nabil H. Mustafa, Saurabh Ray

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

approximation algorithmscomputational geometrygeometric hitting sets

Mathematics Subject Classification ID

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

Recommendations

• Geometric hitting sets for disks: theory and practice
• Tighter estimates for -nets for disks
• Near-linear approximation algorithms for geometric hitting sets
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Near-linear approximation algorithms for geometric hitting sets

Cites work

• -nets and simplex range queries
• Almost optimal set covers in finite VC-dimension
• Almost tight bounds for -nets
• Approximation algorithms for maximum independent set of pseudo-disks
• Fast approximation algorithms for a nonconvex covering problem
• Hitting sets when the VC-dimension is small
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1041084 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Improved results on geometric hitting set problems
• Independent set of intersection graphs of convex objects in 2D
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
• New existence proofs ε-nets
• Reducibility among combinatorial problems
• SCIP: solving constraint integer programs
• Tighter estimates for -nets for disks

Cited in

(20)

• Approximability and hardness of geometric hitting set with axis-parallel rectangles
• Experiments with unit disk cover algorithms for covering massive pointsets
• Near-linear algorithms for geometric hitting sets and set covers
• Near-linear approximation algorithms for geometric hitting sets
• Tighter estimates for -nets for disks
• Geometric hitting sets for disks: theory and practice
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Near-linear approximation algorithms for geometric hitting sets
• Improved results on geometric hitting set problems
• Geometric hitting set for line-constrained disks
• Bounded-degree plane geometric spanners in practice
• On the line-separable unit-disk coverage and related problems
• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
• Simplification of forest classifiers and regressors by sharing branching conditions
• On the line-separable unit-disk coverage and related problems
• On line-separable weighted unit-disk coverage and related problems
• Dynamic geometric set cover, revisited
• Unweighted geometric hitting set for line-constrained disks and related problems
• On line-separable weighted unit-disk coverage and related problems
• An approximation algorithm for submodular hitting set problem with linear penalties

Describes a project that uses

Uses Software

• SCIP
• SoPlex
• CGAL

This page was built for publication: Practical and efficient algorithms for the geometric hitting set problem

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