Deterministic k k -Median Clustering in Near-Optimal Time

Martín Costa, Ermiya Farokhnejad · 2025

Read Deterministic k k -Median Clustering in Near-Optimal Time by Martín Costa, Ermiya Farokhnejad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15115.txt.

Introduction

Martín Costa and Ermiya Farokhnejad present a fixed, non-random method for a classic grouping problem in a 2025 paper. The k-median problem asks for a small set of centers that keeps the total distance from all points to their nearest center as low as possible. It is a standard model for placing services or summing up data.

A known random method solves it near the fastest possible time with a good score, and no method can beat that time by much. Older fixed methods paid for certainty with far worse scores. The authors close much of that gap, matching near-best time while keeping the score within a modest factor. The result matters where repeatable, auditable grouping is required.

Catalog record

CREATORMartín Costa, Ermiya Farokhnejad
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15115

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deterministic k k -Median Clustering in Near-Optimal Time Martín Costa, Ermiya Farokhnejad Abstract The metric k k -median problem is a textbook clustering problem. As input, we are given a metric space V V of size n n and an integer k k , and our task is to find a subset S ⊆ V S\subseteq V of at most k k ‘centers’ that minimizes the total distance from each point in V V to its nearest center in S S . Mettu and Plaxton [UAI’02] gave a randomized algorithm for k k -median that computes a O ⁡ ( 1 ) O(1) -approximation in O ~ ​ ( n ​ k ) \tilde{O}(nk) time. 1 1 1 We use O ~ ​ ( ⋅ ) \tilde{O}(\cdot) to hide polylog factors in the size n n and the aspect ratio Δ \Delta (see Section 2 ) of the metric space. They also showed that any algorithm for this problem with a bounded approximation ratio must have a running time of Ω ⁡ ( n ​ k ) \Omega(nk) . Thus, the running time of their algorithm is optimal up to polylogarithmic factors. For deterministic k k -median, Guha et al. [FOCS’00] gave an algorithm that computes a poly ( log ⁡ ( n / k ) ) \poly(\log(n/k)) -approximation in O ~ ​ ( n ​ k ) \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 k -median algorithm with this running time. This leads us to the following natural question: What is the best approximation of a deterministic k 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 ) ) O(\log(n/k)) -approximation in O ~ ​ ( n ​ k ) \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 ) ) \Omega(\log n/(\log k+\log\log n)) , establishing a gap between the randomized and deterministic settings for k k -median . 1 Introduction Clustering data is one of the fundamental tasks in unsupervised learning. As input, we are given a dataset, and our task is to partition the elements of the dataset into groups called clusters so that similar elements are placed in the same cluster and dissimilar elements are placed in different clusters. One of the basic formulations of clustering is metric k -clustering , where we are given a (weighted) metric space (V,w,d) of size n , and our goal is to find a subset S\subseteq V of at most k centers that minimizes an objective function. We focus on the k -median problem, where the objective is defined as \texttt{cost}(S):=\sum_{x\in V}w(x)\cdot d(x,S) , where d(x,S):=\min_{y\in S}d(x,y) . Equivalently, we want to minimize the total weighted distance from points in V to their nearest center in S . The State-of-the-Art for k -Median. Metric k -median is a fundamental clustering problem with many real-world applications and has been studied extensively across many computational models [ CGTS99 , JV01 , ANFSW19 , BPR+17 , COP03 , AJM09 ] . The problem is NP-Hard and there is a long line of work designing efficient approximation algorithms for k -median using a variety of different techniques, such as local search [ AGK+04 ] and Lagrangian relaxation [ JV01 ] . Mettu and Plaxton gave a randomized algorithm for k -median that computes a O(1) -approximation in \tilde{O}(nk) time [ MP02 ] , where the approximation guarantee holds with high probability. They also showed that any algorithm for this problem with a non-trivial approximation ratio must have a running time of \Omega(nk) . It follows that their algorithm is near-optimal , i.e. optimal up to polylogarithmic factors in the running time and the constant in the approximation ratio. Deterministic Algorithms for k -Median. Designing deterministic algorithms for fundamental problems is an important research direction within algorithms [ CSS23 , HLS24 , ACS22 , NS16 , HLRW24 ] . Even though the randomized complexity of k -median is well understood, we do not have the same understanding of the problem in the deterministic setting. For deterministic k -median, Mettu and Plaxton gave an algorithm that computes a O(1) -approximation in \tilde{O}(n^{2}) time [ MP00 ] , and Jain and Vazirani gave an algorithm with an improved approximation of 6 and a running time of \tilde{O}(n^{2}) [ JV01 ] . Whenever k=\Omega(n) , it follows from the lower bound of [ MP02 ] that these algorithms are near-optimal in both the approximation ratio and running time. On the other hand, for k\ll n , these algorithms are slower than the randomized O(1) -approximation algorithm of [ MP02 ] . Guha et al. gave an algorithm that computes a \poly(\log(n/k)) -approximation in a near-optimal running time of \tilde{O}(nk) [ GMMO00 ] , where the degree of the polynomial in the approximation is unspecified. However, it is not clear how much this approximation ratio can be improved, and in particular, whether or not we can match the bounds for randomized algorithms. This leads us to the following question. Question 1 . What is the best approximation of any deterministic algorithm for k -median that runs in \tilde{O}(nk) time? 1.1 Our Results We make progress in answering 1 by giving a deterministic algorithm with near-optimal running time and an improved approximation of O(\log(n/k)) , proving the following theorem. Theorem 1.1 . There is a deterministic algorithm for k -median that, given a metric space of size n , computes a O(\log(n/k)) -approximate solution in \tilde{O}(nk) time. We obtain our algorithm by adapting the “hierarchical partitioning” approach of Guha et al. [ GMMO00 ] . We show that a modified version of this hierarchy can be implemented efficiently by using “restricted k -clustering” algorithms—a notation that was recently introduced by Bhattacharya et al. to design fast dynamic clustering algorithms [ BCG+24 ] . We design a deterministic algorithm for restricted k -median based on the reverse greedy algorithm of Chrobak et al. [ CKY06 ] and combine it with the hierarchical partitioning framework to construct our algorithm. In addition to our algorithm, we also provide a lower bound on the approximation ratio of any deterministic algorithm with a running time of \tilde{O}(nk) , proving the following theorem. Theorem 1.2 . Any deterministic algorithm for k -median that runs in \tilde{O}(nk) time when given a metric space of size n has an approximation ratio of \Omega\!\left(\frac{\log n}{\log k+\log\log n}\right). This lower bound establishes a separation between the randomized and deterministic settings for k -median —ruling out the possibility of a deterministic O(1) -approximation algorithm that runs in near-optimal \tilde{O}(nk) time for k=n^{o(1)} . For example, when k=\poly(\log n) , Theorem 1.2 shows that any deterministic algorithm with a near-optimal running time must have an approximation ratio of \Omega(\log n/\log\log n) . On the other hand, Theorem 1.1 gives such an algorithm with an approximation ratio

Read the complete text