Exact algorithms and hardness results for geometric red-blue hitting set problem
DOI10.1007/978-3-031-20796-9_13zbMath1528.68387OpenAlexW4313350034MaRDI QIDQ6111475
Raghunath Reddy Madireddy, Subhas C. Nandy, Supantha Pandit
Publication date: 3 August 2023
Published in: Frontiers of Algorithmic Wisdom (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-20796-9_13
intervalspolynomial-time algorithmNP-hardnessAPX-hardnessanchored rectanglesspecial red-blue hitting set
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- An improved algorithm for the red-blue hitting set problem with the consecutive ones property
- Improved results on geometric hitting set problems
- Red-blue covering problems and the consecutive ones property
- Optimal packing and covering in the plane are NP-complete
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- On the geometric red-blue set cover problem
- Geometric red-blue set cover for unit squares and related problems
- A threshold of ln n for approximating set cover
- A PTAS for the Weighted Unit Disk Cover Problem
- PTAS for Weighted Set Cover on Unit Squares
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- On the hardness of approximating minimization problems
- OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
This page was built for publication: Exact algorithms and hardness results for geometric red-blue hitting set problem
