Generalized class cover problem with axis-parallel strips

DOI10.1016/J.COMGEO.2023.102065MaRDI QIDQ6543343zbMATH OpenFDO

Authors Apurva Mudgal, Supantha Pandit

Publication date 24 May 2024

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COMGEO.2023.102065

zbMATH Keywords

approximation algorithmsAPX-hardgeneralized class cover problemgeometric set coverhalf-stripsNP-hardstrips

Mathematics Subject Classification ID

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

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A note on the prize collecting traveling salesman problem
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Almost optimal set covers in finite VC-dimension
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for the class cover problem
• Approximation Schemes for Covering and Packing
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Generalized class cover problem with axis-parallel strips
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 1445322 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• Improved results on geometric hitting set problems
• Optimization, approximation, and complexity classes
• Submodular Function Minimization under Covering Constraints
• The class cover problem with boxes
• Variable-Size Rectangle Covering

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6543343)