2026-07-23T04:32:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20997 2024-09-16T06:02:37Z ddc:004 open_access

Hybrid k-Clustering: Blending k-Median and k-Center Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Saurabh, Saket Zehavi, Meirav clustering k-center k-median Euclidean space fpt approximation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Tanmay Inamdar and Saket Saurabh and Meirav Zehavi 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.4 urn:nbn:de:0030-drops-209975 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.4 eng https://creativecommons.org/licenses/by/4.0/legalcode