2026-07-22T21:35:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12875 2024-03-06T10:50:58Z ddc:004 open_access

Improved Bounds for Metric Capacitated Covering Problems Bandyapadhyay, Sayan Capacitated covering approximation algorithms bicriteria approximation LP rounding 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.9 urn:nbn:de:0030-drops-128759 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode