The class cover problem with boxes
From MaRDI portal
Publication:419500
DOI10.1016/j.comgeo.2012.01.014zbMath1239.65015OpenAlexW2161667053MaRDI QIDQ419500
Sergio Cabello, José-Miguel Díaz-Báñez, Sergey Bereg, Carlos Seara, Inmaculada Ventura, Pablo Pérez-Lantero
Publication date: 18 May 2012
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.01.014
classificationalgorithmscoveringNP-hardnessboxesgeometric optimization\(\varepsilon\)-netsclass cover
Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items
Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions, The board packing problem, Classifying negative and positive points by optimal box clustering, On the geometric red-blue set cover problem, Computing the coarseness with strips or boxes, Classification using proximity catch digraphs
Cites Work
- Unnamed Item
- Improved approximation algorithms for geometric set cover
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- Geometric complexity of some location problems
- Approximation algorithms for the class cover problem
- Almost optimal set covers in finite VC-dimension
- A threshold of ln n for approximating set cover
- The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
- Covering Polygons Is Hard
- SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Tight lower bounds for the size of epsilon-nets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
