Bandyapadhyay, Sayan
Improved Bounds for Metric Capacitated Covering Problems
Abstract
In the Metric Capacitated Covering (MCC) problem, given a set of balls ℬ in a metric space P with metric d and a capacity parameter U, the goal is to find a minimum sized subset ℬ' ⊆ ℬ and an assignment of the points in P to the balls in ℬ' such that each point is assigned to a ball that contains it and each ball is assigned with at most U points. MCC achieves an O(log P)approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of o(log P) even with β < 3 factor expansion of the balls. Bandyapadhyay et al. [SoCG 2018, DCG 2019] showed that one can obtain an O(1)approximation for the problem with 6.47 factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound 3 and the upper bound 6.47. In this current work, we show that it is possible to obtain an O(1)approximation with only 4.24 factor expansion of the balls. We also show a similar upper bound of 5 for a more generalized version of MCC for which the best previously known bound was 9.
BibTeX  Entry
@InProceedings{bandyapadhyay:LIPIcs:2020:12875,
author = {Sayan Bandyapadhyay},
title = {{Improved Bounds for Metric Capacitated Covering Problems}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {9:19:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12875},
URN = {urn:nbn:de:0030drops128759},
doi = {10.4230/LIPIcs.ESA.2020.9},
annote = {Keywords: Capacitated covering, approximation algorithms, bicriteria approximation, LP rounding}
}
26.08.2020
Keywords: 

Capacitated covering, approximation algorithms, bicriteria approximation, LP rounding 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 