A constant-factor approximation for multi-covering with disks

DOI10.20382/JOCG.V6I1A9MaRDI QIDQ2970422zbMATH OpenOpenAlexFDO

Authors Santanu Bhowmick, Shi-Ke Xue, Kasturi Varadarajan

Publication date 30 March 2017

Full work available at URL https://arxiv.org/abs/1407.5674

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $kappa:XightarrowmathcalN$, and a constant $alphageq1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $xinX$ be covered by at least $kappa(x)$ of the server disks. The objective function we wish to minimize is the sum of the $alpha$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.

Recommendations

• A constant-factor approximation for multi-covering with disks
• A note on multicovering with disks
• Polynomial time approximation schemes for minimum disk cover problems
• Covering Points by Unit Disks of Fixed Location
• An improved approximation algorithm for the most points covering problem

Cited in

(16)

• Anchored rectangle and square packings
• A note on multicovering with disks
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• A primal-dual algorithm for the minimum power partial cover problem
• Fault-tolerant covering problems in metric spaces
• Minimum power partial multi-cover on a line
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• Multiobjective Disk Cover Admits a PTAS
• Covering moving points with anchored disks
• A constant-factor approximation for multi-covering with disks
• An improved approximation algorithm for the k-prize-collecting minimum power cover problem
• An approximation algorithm for the minimum soft capacitated disk multi-coverage problem
• PTAS for minimum cost multicovering with disks
• Worst-case optimal covering of rectangles by disks
• An improved approximation algorithm for the most points covering problem

This page was built for publication: A constant-factor approximation for multi-covering with disks

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