License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.62
URN: urn:nbn:de:0030-drops-129288
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12928/
Go to the corresponding LIPIcs Volume Portal

Inamdar, Tanmay ; Varadarajan, Kasturi

Capacitated Sum-Of-Radii Clustering: An FPT Approximation

pdf-format:
LIPIcs-ESA-2020-62.pdf (0.5 MB)

Abstract

In sum of radii clustering, the input consists of a finite set of points in a metric space. The problem asks to place a set of k balls centered at a subset of the points such that every point is covered by some ball, and the objective is to minimize the sum of radii of these balls. In the capacitated version of the problem, we want to assign each point to a ball containing it, such that no ball is assigned more than U points, where U denotes the capacity of the points. While constant approximations are known for the uncapacitated version of the problem, there is no work on the capacitated version. We make progress on this problem by obtaining a constant approximation using a Fixed Parameter Tractable (FPT) algorithm. In particular, the running time of the algorithm is of the form 2^O(k²) ⋅ n^O(1). As a warm-up for this result, we also give a constant approximation for the uncapacitated sum of radii clustering problem with matroid constraints, thus obtaining the first FPT approximation for this problem.

BibTeX - Entry

@InProceedings{inamdar_et_al:LIPIcs:2020:12928,
  author =	{Tanmay Inamdar and Kasturi Varadarajan},
  title =	{{Capacitated Sum-Of-Radii Clustering: An FPT Approximation}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{62:1--62:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12928},
  URN =		{urn:nbn:de:0030-drops-129288},
  doi =		{10.4230/LIPIcs.ESA.2020.62},
  annote =	{Keywords: Sum-of-radii Clustering, Capacitated Clustering}
}

Keywords: Sum-of-radii Clustering, Capacitated Clustering
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI