A PTAS for the cardinality constrained covering with unit balls

DOI10.1016/j.tcs.2014.01.026zbMath1282.68194OpenAlexW2093747735MaRDI QIDQ2437774

Mohammadreza Razzazi, Taha Ghasemi

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

zbMATH Keywords

computational geometrycapacitated coveringcardinality constrained coveringcovering with disksfully polynomial time approximation algorithm

Mathematics Subject Classification ID

Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Approximation algorithms (68W25)

Related Items (4)

Capacitated covering problems in geometric spaces ⋮ Improved bounds for metric capacitated covering problems ⋮ Unnamed Item ⋮ Capacitated Covering Problems in Geometric Spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering many or few points with unit disks
• Improved approximation algorithms for geometric set cover
• Optimal packing and covering in the plane are NP-complete
• Covering a set of points in multidimensional space
• Exact and approximation algorithms for clustering
• An analysis of the greedy algorithm for the submodular set covering problem
• Almost optimal set covers in finite VC-dimension
• WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
• Covering Problems with Hard Capacities
• Dependent rounding and its applications to approximation algorithms
• Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• How to Allocate Network Centers
• Capacitated vertex covering
• The Capacitated K-Center Problem
• On the set multi-cover problem in geometric settings
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Theory and Application of Width Bounded Geometric Separator
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: A PTAS for the cardinality constrained covering with unit balls