文章基本信息

标题：Capacitated Sum-Of-Radii Clustering: An FPT Approximation
本地全文：下载
作者：Tanmay Inamdar ; Kasturi Varadarajan
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：62:1-62:17
DOI：10.4230/LIPIcs.ESA.2020.62
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Sum-of-radii Clustering; Capacitated Clustering