eng
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Leibniz International Proceedings in Informatics
1868-8969
2024-09-16
4:1
4:19
10.4230/LIPIcs.APPROX/RANDOM.2024.4
article
Hybrid k-Clustering: Blending k-Median and k-Center
Fomin, Fedor V.
1
https://orcid.org/0000-0003-1955-4612
Golovach, Petr A.
1
https://orcid.org/0000-0002-2619-2990
Inamdar, Tanmay
2
https://orcid.org/0000-0002-0184-5932
Saurabh, Saket
3
1
https://orcid.org/0000-0001-7847-6402
Zehavi, Meirav
4
https://orcid.org/0000-0002-3636-5322
University of Bergen, Norway
Indian Institute of Technology Jodhpur, Jodhpur, India
The Institute of Mathematical Sciences, HBNI, Chennai, India
Ben-Gurion University of the Negev, Beer-Sheva, Israel
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clustering problem, given a set P of points in ℝ^d, an integer k, and a non-negative real r, our objective is to position k closed balls of radius r to minimize the sum of distances from points not covered by the balls to their closest balls. Equivalently, we seek an optimal L₁-fitting of a union of k balls of radius r to a set of points in the Euclidean space. When r = 0, this corresponds to k-median; when the minimum sum is zero, indicating complete coverage of all points, it is k-center.
Our primary result is a bicriteria approximation algorithm that, for a given ε > 0, produces a hybrid k-clustering with balls of radius (1+ε)r. This algorithm achieves a cost at most 1+ε of the optimum, and it operates in time 2^{(kd/ε)^𝒪(1)} ⋅ n^𝒪(1). Notably, considering the established lower bounds on k-center and k-median, our bicriteria approximation stands as the best possible result for Hybrid k-Clustering.
https://drops.dagstuhl.de/storage/00lipics/lipics-vol317-approx-random2024/LIPIcs.APPROX-RANDOM.2024.4/LIPIcs.APPROX-RANDOM.2024.4.pdf
clustering
k-center
k-median
Euclidean space
fpt approximation