Exact and approximation algorithms for geometric and capacitated set cover problems
DOI10.1007/S00453-011-9591-5zbMATH Open1252.68347OpenAlexW2794433803MaRDI QIDQ1759660FDOQ1759660
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
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
approximation algorithmsexact algorithmsAPX-hardnesspolynomial-time approximation schemeset covertime complexitygeometric set coverassignment of directional antennacapacitated set covershipping with deadlines
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Almost optimal set covers in finite VC-dimension
- Improved approximation algorithms for geometric set cover
- Approximation schemes for covering and packing problems in image processing and VLSI
- Resource constrained scheduling as generalized bin packing
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- An efficient fully polynomial approximation scheme for the Subset-Sum problem.
Cited In (10)
- 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
- Universal approximations for TSP, Steiner tree, and set cover
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)
