Hybrid k-Clustering: Blending k-Median and k-Center
<|reference_start|>Hybrid k-Clustering: Blending k-Median and k-Center: 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_1-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 \epsilon>0, produces a hybrid k-clustering with balls of radius (1+\epsilon)r. This algorithm achieves a cost at most 1+\epsilon of the optimum, and it operates in time 2^{(kd/\epsilon)^{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.<|reference_end|>
@article{fomin2024hybrid,
    title={Hybrid k-Clustering: Blending k-Median and k-Center},
    author={Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and
  Meirav Zehavi},
    journal={arXiv preprint arXiv:2407.08295},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.08295},
    primaryClass={cs.DS cs.CG}
}