Exact and approximation algorithms for geometric and capacitated set cover problems

DOI10.1007/s00453-011-9591-5zbMath1252.68347OpenAlexW2794433803MaRDI 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 complexityapproximation algorithmsset coverpolynomial-time approximation schemeexact algorithmsAPX-hardnessgeometric set coverassignment of directional antennacapacitated set covershipping with deadlines

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40)

Related Items (2)

Capacitated covering problems in geometric spaces ⋮ 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

This page was built for publication: Exact and approximation algorithms for geometric and capacitated set cover problems