{"ID":2834222,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.03304","arxiv_id":"2512.03304","title":"Fast approximate $\\ell$-center clustering in high dimensional spaces","abstract":"We study the design of efficient approximation algorithms for the $\\ell$-center clustering and minimum-diameter $\\ell$-clustering problems in high dimensional Euclidean and Hamming spaces. Our main tool is randomized dimension reduction. First, we present a general method of reducing the dependency of the running time of a hypothetical algorithm for the $\\ell$-center problem in a high dimensional Euclidean space on the dimension size. Utilizing in part this method, we provide $(2+ε)$- approximation algorithms for the $\\ell$-center clustering and minimum-diameter $\\ell$-clustering problems in Euclidean and Hamming spaces that are substantially faster than the known $2$-approximation ones when both $\\ell$ and the dimension are super-logarithmic. Next, we apply the general method to the recent fast approximation algorithms with higher approximation guarantees for the $\\ell$-center clustering problem in a high dimensional Euclidean space. Finally, we provide a speed-up of the known $O(1)$-approximation method for the generalization of the $\\ell$-center clustering problem to include $z$ outliers (i.e., $z$ input points can be ignored while computing the maximum distance of an input point to a center) in high dimensional Euclidean and Hamming spaces.","short_abstract":"We study the design of efficient approximation algorithms for the $\\ell$-center clustering and minimum-diameter $\\ell$-clustering problems in high dimensional Euclidean and Hamming spaces. Our main tool is randomized dimension reduction. First, we present a general method of reducing the dependency of the running time...","url_abs":"https://arxiv.org/abs/2512.03304","url_pdf":"https://arxiv.org/pdf/2512.03304v1","authors":"[\"Mirosław Kowaluk\",\"Andrzej Lingas\",\"Mia Persson\"]","published":"2025-12-02T23:38:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}