Exact and approximation algorithms for geometric and capacitated set cover problems

DOI10.1007/s00453-011-9591-5zbMath1252.68347MaRDI QIDQ1759660

Piotr Berman, Andrzej Lingas, Marek Karpinski

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9591-5

zbMATH Keywords

time complexity; approximation algorithms; set cover; polynomial-time approximation scheme; exact algorithms; APX-hardness; geometric set cover; assignment of directional antenna; capacitated set cover; shipping with deadlines

Mathematics Subject Classification ID

90C27: Combinatorial optimization

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

05B40: Combinatorial aspects of packing and covering

Related Items

Unnamed Item, Capacitated covering problems in geometric spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Resource constrained scheduling as generalized bin packing
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Almost optimal set covers in finite VC-dimension
• Approximation schemes for covering and packing problems in image processing and VLSI
• Improved approximation algorithms for geometric set cover
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes