A PTAS for the cardinality constrained covering with unit balls
DOI10.1016/J.TCS.2014.01.026zbMATH Open1282.68194OpenAlexW2093747735MaRDI QIDQ2437774FDOQ2437774
Authors: Taha Ghasemi, Mohammadreza Razzazi 
Publication date: 13 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.026
Recommendations
- PTAS for weighted set cover on unit squares
- On capacitated covering with unit balls
- A PTAS for the Weighted Unit Disk Cover Problem
- A unified approach to approximating partial covering problems
- A Unified Approach to Approximating Partial Covering Problems
- PTAS for connected vertex cover in unit disk graphs
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Bin covering with cardinality constraints
- PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
computational geometrycapacitated coveringcardinality constrained coveringcovering with disksfully polynomial time approximation algorithm
Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)
Cites Work
- Introduction to algorithms
- An analysis of the greedy algorithm for the submodular set covering problem
- Almost optimal set covers in finite VC-dimension
- Title not available (Why is that?)
- How to Allocate Network Centers
- The Capacitated K-Center Problem
- Capacitated vertex covering
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Exact and approximation algorithms for clustering
- Approximation schemes for covering and packing problems in image processing and VLSI
- Dependent rounding and its applications to approximation algorithms
- Title not available (Why is that?)
- Exact and approximation algorithms for geometric and capacitated set cover problems
- Optimal packing and covering in the plane are NP-complete
- WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
- Improved approximation algorithms for geometric set cover
- Covering a set of points in multidimensional space
- Minimum-cost coverage of point sets by disks
- On the set multi-cover problem in geometric settings
- Covering Problems with Hard Capacities
- An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
- Theory and Application of Width Bounded Geometric Separator
- Covering many or few points with unit disks
- Title not available (Why is that?)
Cited In (6)
This page was built for publication: A PTAS for the cardinality constrained covering with unit balls
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437774)
