Hybrid k-Clustering: Blending k-Median and k-Center

2024/07/11 by Fomin, Fedor V., Golovach, Petr A., Inamdar, Tanmay +2
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2407.08295

Abstract

We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clusetring problem, given a set P of points in R^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/ε)^O(1) n^O(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-Clusetring.

Related

• Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
• A General Hybrid Clustering Technique
• Individual Fairness for k-Clustering
• Ball k-means
• Faster Algorithms for the Constrained k-means Problem