A PTAS for the cardinality constrained covering with unit balls

DOI10.1016/J.TCS.2014.01.026MaRDI QIDQ2437774zbMATHOpenAlexFDO

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

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) Approximation algorithms (68W25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

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

Cites work

• scientific article; zbMATH DE number 2038708 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• Almost optimal set covers in finite VC-dimension
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Capacitated vertex covering
• Covering Problems with Hard Capacities
• Covering a set of points in multidimensional space
• Covering many or few points with unit disks
• Dependent rounding and its applications to approximation algorithms
• Exact and approximation algorithms for clustering
• Exact and approximation algorithms for geometric and capacitated set cover problems
• How to Allocate Network Centers
• Improved approximation algorithms for geometric set cover
• Introduction to algorithms
• Minimum-cost coverage of point sets by disks
• On the set multi-cover problem in geometric settings
• Optimal packing and covering in the plane are NP-complete
• The Capacitated K-Center Problem
• Theory and Application of Width Bounded Geometric Separator
• Weighted geometric set cover problems revisited

Cited in

(6)

• Variants of Euclidean \(k\)-center clusterings
• Capacitated covering problems in geometric spaces
• scientific article; zbMATH DE number 7651148 (Why is no real title available?)
• Improved bounds for metric capacitated covering problems
• Capacitated covering problems in geometric spaces
• On capacitated covering with unit balls

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)