Fast approximate $\ell$-center clustering in high dimensional spaces
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909941660385280 |
|---|---|
| author | Kowaluk, Mirosław Lingas, Andrzej Persson, Mia |
| author_facet | Kowaluk, Mirosław Lingas, Andrzej Persson, Mia |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03304 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast approximate $\ell$-center clustering in high dimensional spaces Kowaluk, Mirosław Lingas, Andrzej Persson, Mia Data Structures and Algorithms F.2.2 F.2.2 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. |
| title | Fast approximate $\ell$-center clustering in high dimensional spaces |
| topic | Data Structures and Algorithms F.2.2 F.2.2 |
| url | https://arxiv.org/abs/2512.03304 |