Capacitated covering problems in geometric spaces

DOI10.1007/S00454-019-00127-5MaRDI QIDQ2189730zbMATH OpenOpenAlexWikidataFDO

Authors Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, Kasturi Varadarajan

Publication date 16 June 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.05170, https://drops.dagstuhl.de/opus/volltexte/2018/8720/

zbMATH Keywords

bi-criteria approximationcapacitated coveringgeometric set coverLP rounding

Mathematics Subject Classification ID

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

Abstract: In this article, we consider the following capacitated covering problem. We are given a set $P$ of $n$ points and a set $mathcalB$ of balls from some metric space, and a positive integer $U$ that represents the capacity of each of the balls in $mathcalB$. We would like to compute a subset $mathcal{B}^{\prime }subseteqmathcalB$ of balls and assign each point in $P$ to some ball in $mathcalB$ that contains it, such that the number of points assigned to any ball is at most $U$. The objective function that we would like to minimize is the cardinality of $mathcalB$. We consider this problem in arbitrary metric spaces as well as Euclidean spaces of constant dimension. In the metric setting, even the uncapacitated version of the problem is hard to approximate to within a logarithmic factor. In the Euclidean setting, the best known approximation guarantee in dimensions $3$ and higher is logarithmic in the number of points. Thus we focus on obtaining "bi-criteria" approximations. In particular, we are allowed to expand the balls in our solution by some factor, but optimal solutions do not have that flexibility. Our main result is that allowing constant factor expansion of the input balls suffices to obtain constant approximations for these problems. In fact, in the Euclidean setting, only $(1+epsilon)$ factor expansion is sufficient for any $epsilon>0$, with the approximation factor being a polynomial in $1/epsilon$. We obtain these results using a unified scheme for rounding the natural LP relaxation; this scheme may be useful for other capacitated covering problems. We also complement these bi-criteria approximations by obtaining hardness of approximation results that shed light on our understanding of these problems.

Recommendations

• Capacitated covering problems in geometric spaces
• On capacitated covering with unit balls
• Capacitated discrete unit disk cover
• Exact and approximation algorithms for geometric and capacitated set cover problems
• Exact and approximation algorithms for geometric and capacitated set cover problems

Cites work

• A PTAS for the cardinality constrained covering with unit balls
• Algorithms - ESA 2003
• Almost optimal set covers in finite VC-dimension
• An analysis of the greedy algorithm for the submodular set covering problem
• An improved approximation algorithm for vertex cover with hard capacities
• Analytical approach to parallel repetition
• Approximation schemes for covering and packing problems in image processing and VLSI
• Capacitated domination problems on planar graphs
• Centrality of trees for capacitated \(k\)-center
• Covering Problems with Hard Capacities
• Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
• Exact and approximation algorithms for geometric and capacitated set cover problems
• How to Allocate Network Centers
• Improved approximation algorithms for geometric set cover
• Improved results on geometric hitting set problems
• Iterative partial rounding for vertex cover with hard capacities
• LP-based algorithms for capacitated facility location
• LP-based approximation algorithms for capacitated facility location
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Packing and covering with non-piercing regions
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Replica placement on bounded treewidth graphs
• Small-size -nets for axis-parallel rectangles and boxes
• Switching to directional antennas with constant increase in radius and hop distance
• The Capacitated K-Center Problem
• The hardness of approximation: Gap location
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover problems revisited
• Weighted geometric set cover via quasi-uniform sampling

Cited in

(7)

• Exact and approximation algorithms for geometric and capacitated set cover problems
• Capacitated covering problems in geometric spaces
• On capacitated covering with unit balls
• Capacitated discrete unit disk cover
• Energy-constrained geometric coverage problem
• An approximation algorithm for the minimum soft capacitated disk multi-coverage problem
• Bicriteria approximation algorithms for the unit disk coverage problem

This page was built for publication: Capacitated covering problems in geometric spaces

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