Exact and approximation algorithms for geometric and capacitated set cover problems

DOI10.1007/S00453-011-9591-5MaRDI QIDQ1759660zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsexact algorithmsAPX-hardnesspolynomial-time approximation schemeset covertime complexitygeometric set coverassignment of directional antennacapacitated set covershipping with deadlines

Mathematics Subject Classification ID

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

Recommendations

• Exact and approximation algorithms for geometric and capacitated set cover problems
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Capacitated discrete unit disk cover
• Capacitated covering problems in geometric spaces
• Weighted geometric set multi-cover via quasi-uniform sampling

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Almost optimal set covers in finite VC-dimension
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Approximation schemes for covering and packing problems in image processing and VLSI
• Improved approximation algorithms for geometric set cover
• Resource constrained scheduling as generalized bin packing
• Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes

Cited in

(10)

• Universal approximations for TSP, Steiner tree, and set cover
• Capacitated discrete unit disk cover
• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Algorithms of optimal set covering on the planar R^2
• Geometric dominating-set and set-cover via local-search
• Capacitated covering problems in geometric spaces
• Capacitated covering problems in geometric spaces
• Exact and approximation algorithms for geometric and capacitated set cover problems

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

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