Deterministic $k$-Median Clustering in Near-Optimal Time
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914428058861568 |
|---|---|
| author | Costa, Martín Farokhnejad, Ermiya |
| author_facet | Costa, Martín Farokhnejad, Ermiya |
| contents | The metric $k$-median problem is a textbook clustering problem. As input, we are given a metric space $V$ of size $n$ and an integer $k$, and our task is to find a subset $S \subseteq V$ of at most $k$ `centers' that minimizes the total distance from each point in $V$ to its nearest center in $S$.
Mettu and Plaxton [UAI'02] gave a randomized algorithm for $k$-median that computes a $O(1)$-approximation in $\tilde O(nk)$ time. They also showed that any algorithm for this problem with a bounded approximation ratio must have a running time of $Ω(nk)$. Thus, the running time of their algorithm is optimal up to polylogarithmic factors.
For deterministic $k$-median, Guha et al.~[FOCS'00] gave an algorithm that computes a $\text{poly}(\log (n/k))$-approximation in $\tilde O(nk)$ time, where the degree of the polynomial in the approximation is unspecified. To the best of our knowledge, this remains the state-of-the-art approximation of any deterministic $k$-median algorithm with this running time.
This leads us to the following natural question: What is the best approximation of a deterministic $k$-median algorithm with near-optimal running time? We make progress in answering this question by giving a deterministic algorithm that computes a $O(\log(n/k))$-approximation in $\tilde O(nk)$ time. We also provide a lower bound showing that any deterministic algorithm with this running time must have an approximation ratio of $Ω(\log n/(\log k + \log \log n))$, establishing a gap between the randomized and deterministic settings for $k$-median. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15115 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic $k$-Median Clustering in Near-Optimal Time Costa, Martín Farokhnejad, Ermiya Data Structures and Algorithms The metric $k$-median problem is a textbook clustering problem. As input, we are given a metric space $V$ of size $n$ and an integer $k$, and our task is to find a subset $S \subseteq V$ of at most $k$ `centers' that minimizes the total distance from each point in $V$ to its nearest center in $S$. Mettu and Plaxton [UAI'02] gave a randomized algorithm for $k$-median that computes a $O(1)$-approximation in $\tilde O(nk)$ time. They also showed that any algorithm for this problem with a bounded approximation ratio must have a running time of $Ω(nk)$. Thus, the running time of their algorithm is optimal up to polylogarithmic factors. For deterministic $k$-median, Guha et al.~[FOCS'00] gave an algorithm that computes a $\text{poly}(\log (n/k))$-approximation in $\tilde O(nk)$ time, where the degree of the polynomial in the approximation is unspecified. To the best of our knowledge, this remains the state-of-the-art approximation of any deterministic $k$-median algorithm with this running time. This leads us to the following natural question: What is the best approximation of a deterministic $k$-median algorithm with near-optimal running time? We make progress in answering this question by giving a deterministic algorithm that computes a $O(\log(n/k))$-approximation in $\tilde O(nk)$ time. We also provide a lower bound showing that any deterministic algorithm with this running time must have an approximation ratio of $Ω(\log n/(\log k + \log \log n))$, establishing a gap between the randomized and deterministic settings for $k$-median. |
| title | Deterministic $k$-Median Clustering in Near-Optimal Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.15115 |