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

DOI10.1016/J.DAM.2016.03.006MaRDI QIDQ335346zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• Approximation algorithms for hitting objects with straight lines
• Approximation algorithms for the class cover problem
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Generalized class cover problem with axis-parallel strips
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• Improved results on geometric hitting set problems
• On column-restricted and priority covering integer programs
• Orthogonal segment stabbing
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• The class cover problem with boxes
• The prize collecting traveling salesman problem
• Variable-Size Rectangle Covering

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)