Generalized class cover problem with axis-parallel strips

DOI10.1016/j.comgeo.2023.102065MaRDI QIDQ6543343

Apurva Mudgal, Supantha Pandit

Publication date: 24 May 2024

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

NP-hardapproximation algorithmsstripsAPX-hardgeometric set coverhalf-stripsgeneralized class cover problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Mathematical programming (90Cxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• The class cover problem with boxes
• Improved results on geometric hitting set problems
• A note on the prize collecting traveling salesman problem
• Improved approximation algorithms for geometric set cover
• Optimization, approximation, and complexity classes
• Approximation algorithms for the class cover problem
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Almost optimal set covers in finite VC-dimension
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• Variable-Size Rectangle Covering
• Approximation Schemes for Covering and Packing
• Submodular Function Minimization under Covering Constraints
• Generalized Class Cover Problem with Axis-Parallel Strips

This page was built for publication: Generalized class cover problem with axis-parallel strips