1 Search Results for "Bhowmick, Santanu"

Document
DOI: 10.4230/LIPIcs.SoCG.2018.7
Capacitated Covering Problems in Geometric Spaces

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

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
In this article, we consider the following capacitated covering problem. We are given a set P of n points and a set B of balls from some metric space, and a positive integer U that represents the capacity of each of the balls in B. We would like to compute a subset B' subseteq B of balls and assign each point in P to some ball in B' 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 B'. 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 this problem. 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.
Cite as

Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, and Kasturi Varadarajan. Capacitated Covering Problems in Geometric Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2018.7,
  author =	{Bandyapadhyay, Sayan and Bhowmick, Santanu and Inamdar, Tanmay and Varadarajan, Kasturi},
  title =	{{Capacitated Covering Problems in Geometric Spaces}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.7},
  URN =		{urn:nbn:de:0030-drops-87205},
  doi =		{10.4230/LIPIcs.SoCG.2018.7},
  annote =	{Keywords: Capacitated covering, Geometric set cover, LP rounding, Bi-criteria approximation}
}
  • Refine by Author
  • 1 Bandyapadhyay, Sayan
  • 1 Bhowmick, Santanu
  • 1 Inamdar, Tanmay
  • 1 Varadarajan, Kasturi

  • Refine by Classification

  • Refine by Keyword
  • 1 Bi-criteria approximation
  • 1 Capacitated covering
  • 1 Geometric set cover
  • 1 LP rounding

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact