Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions

DOI10.1016/j.dam.2016.03.006zbMath1348.05050OpenAlexW2343352288MaRDI QIDQ335346

Apurva Mudgal, Supantha Pandit

Publication date: 2 November 2016

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

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

zbMATH Keywords

NP-completenessgeneralized class covergeometric hitting setgeometric set coverhalf-stripsopposite directions

Mathematics Subject Classification ID

Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of packing and covering (05B40)

Related Items (3)

Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Unique Coverage with Rectangular Regions

Cites Work

• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• The class cover problem with boxes
• Improved results on geometric hitting set problems
• Orthogonal segment stabbing
• Approximation algorithms for hitting objects with straight lines
• Approximation algorithms for the class cover problem
• On Column-Restricted and Priority Covering Integer Programs
• Variable-Size Rectangle Covering
• The prize collecting traveling salesman problem
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Generalized Class Cover Problem with Axis-Parallel Strips

This page was built for publication: Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions