Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
DOI10.1016/J.DAM.2016.03.006zbMATH Open1348.05050OpenAlexW2343352288MaRDI QIDQ335346FDOQ335346
Authors: 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
Recommendations
- \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
- Covering, hitting, piercing and packing rectangles intersecting an inclined line
- Minimum membership covering and hitting
- New results on a family of geometric hitting set problems in the plane
- On the hardness of some geometric optimization problems with rectangles
NP-completenessgeneralized class covergeometric hitting setgeometric set coverhalf-stripsopposite directions
Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of packing and covering (05B40)
Cites Work
- Approximation algorithms for the class cover problem
- The prize collecting traveling salesman problem
- Planar Formulae and Their Uses
- The Problem of Compatible Representatives
- Improved results on geometric hitting set problems
- Approximation algorithms for hitting objects with straight lines
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- On column-restricted and priority covering integer programs
- Variable-Size Rectangle Covering
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- The class cover problem with boxes
- Generalized class cover problem with axis-parallel strips
- Orthogonal segment stabbing
Cited In (6)
- \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
- Exact algorithms and hardness results for geometric red-blue hitting set problem
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- Unique coverage with rectangular regions
- Generalized class cover problem with axis-parallel strips
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q335346)
