Faster Approximation Algorithms for k-Center via Data Reduction
Authors: Arnold Filtser
Shaofeng H.-C. Jiang
Yi Li
Anurag Murty Naredla
Ioannis Psarros
Qiaoyuan Yang
Qin Zhang
Venue: ICML 2025 poster (2025)
Keywords: k-center
clustering
Euclidean
high dimension
coreset
Primary area: theory
TL;DR: Near-linear time O(1)-approximation for k-center for large k = n^c (0 < c < 1) regime, via new coreset and geometric hashing techniques.

Abstract: We study efficient algorithms for the Euclidean $k$-Center problem, focusing on the regime of large $k$. We take the approach of data reduction by considering $\alpha$-coreset, which is a small subset $S$ of the dataset $P$ such that any $\beta$-approximation on $S$ is an $(\alpha + \beta)$-approximation on $P$. We give efficient algorithms to construct coresets whose size is $k \cdot o(n)$, which immediately speeds up existing approximation algorithms. Notably, we obtain a near-linear time $O(1)$-approximation when $k = n^c$ for any $0 < c < 1$. We validate the performance of our coresets on real-world datasets with large $k$, and we observe that the coreset speeds up the well-known Gonzalez algorithm by up to $4$ times, while still achieving similar clustering cost. Technically, one of our coreset results is based on a new efficient construction of consistent hashing with competitive parameters. This general tool may be of independent interest for algorithm design in high dimensional Euclidean spaces.

Faster Approximation Algorithms for k- k-Center via Data Reduction
Arnold Filtser'
Shaofeng H.-C. Jiang? Li Anurag Murty Naredla Ioannis Psarros Qiaoyuan Yang"
Qin Zhang
Abstract
chine learning. In d--CENTER, the input is dataset P S Rd of points and parameter k. The goal is to find a set C S Rd (called centers) with |C| = k that minimizes the cost function
We study efficient algorithms for the Euclidean k-- k-Center problem, focusing on the regime of large k. We take the approach of data reduction by con- sidering a-coreset, which is a small subset S of the dataset P such that any (-approximation on S is an (a + -paappooxinttion on P. We give efficient algorithms to construct coresets whose size is k: o(n), which immediately speeds up ex- isting approximation algorithms. Notably, ob- tain near-linear time ((1) apprroxxoxinaoo when k ==n" for any 0 < c < 1. We validate the perfor- mance of our coresets on real-world datasets with large k, and we observe that the coreset speeds up the well-known Gonzalez algorithm by up to times, while still achieving similar clustering cost. Technically, based on new efficient construction of consis- tent hashing with competitive parameters. This general tool may be of independent interest for algorithm design in high dimensional Euclidean spaces.
cost cost(P,C), := max dist(p, C)2, PEP
where dist(p, 4) := lp Ell2 and dist(p. C) min.eo dist (p. c). The k-CENTER problem presents sub- stantial computational challenges and remains APX-hard even when d O(1) (Feder Greene, 1988).
The study of efficient approximation algorithms for k- CENTER dates back to the 1980s, with several algorithms providing 2-approximations (Gonzalez, 1985; Hochbaum & Shmoys, 1985; 1986). Among these, the classic algorithm of Gonzalez (Gonzalez, 1985) runs in ((kkd) time. While it achieves good performance for k = (1), its ((nk) de- pendence renders much less efficient for large k. In fact, large values of k in k-clustering are increasingly relevant in modern applications such as product quantization for near- est neighbor search (Jégou et al., 201 1) in vector databases. This has motivated algorithmic studies for the large k regime for k-clustering in various computational models (Ene et al., 2011; Bateni et al., 2021: Coy et al., 2023; Czumaj et al., 2024; la Tour Saulpic, 2024). The record linkage problem, also known as entity resolution or reference reconciliation, has been subject of study in databases for decades (Koudas et al., 2006; Herzog et al., 2007; Dong & Naumann, 2009). This problem can also be viewed as a k-center clustering problem, where k represents the number of ground truth entities and often very large.
of our coreset results is
1. Introduction
The k- C-CENTER problem is a fundamental clustering prob- lem that has been extensively studied in various areas, in- cluding combinatorial optimization, data science, and ma-
The authors are listed in alphabetical order. 'Computer Science Department, Bar-Ilan University "School of Com- puter Science, Peking University 'College of Computing and Data Science, Nanyang Technological University 'Institut für Informatik. University of Bonn 'Archimedes, Athena Research Center "Luddy School of Informatics, Computing, and Engineering, Indiana University Bloomington. Corre- spondence to: Arnold Filtser <amold. filtllrffffereeeee @ il. Shaofeng H.-.. Jiang <shaofeng, jahaafeng.jiange @ @pk.epkkueee liku.edu.cn'>. Yi Li <yili @ ntw.edu.sg>, Anurag Murty Naredla <anuragmurty @ uni- bonn.de>, loannis Psarros <ipsarros @ athenarc.gr" Qiaoyuan Yang <qiaoyuanyang www.tt.kku.uuuu...... Zhang <qchangcs@iu.du>>
For the large-k regime, is possible to obtain a subquadratic (n²-v= time! (2 +2+ general ratio-time trade-off Ö( 11/62) time (Eppstein et al., 2020)3. Yet, it is un-
algorithm², and ((pprrxppoxiitttiin in
'Throughout the paper. the Ó-notation hides the dependence poly n)....
"This can be obtained by combining an O(n"~ v (1 O(e)) apprrxiatto r-net construction (Avarikioti al., 2020) with standard reduction E-CENTER net constructions (Hochbaum & Shmoys, 1986).
Qin
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'A similar tradeoff can also be achieved via running O(1)- approximation for sparse graphs (Thorup, 2004) Euclidean spanner (Har-Peled et al., 2013).

---

Faster Approximation Algorithms for k-Center via Data Reduction
known if these trade-offs can be improved. The ideal goal is to design O11aapproximmatinn in near-linear time O(n), which would directly improve the original Gonzalez's s run- time by removing an (kk) factor. However, this seems to be challenging with current techniques. Indeed, even the apparently easier task of finding an O(J)aapproximation to the cost of a given center set C, without optimizing C, in near-linear (n) time remains unsolved.
new hashing result may be useful for algorithm design in high-dimensional Fuclidean spaces in general. Finally, we remark that our coreset in Theorem 1.1 may be applied re- cursively to further reduce the coreset size; see Appendix D for a detailed discussion.
Our second coreset (Theorem 1.2) has size ((k), which is independent of a, but has larger O(nk"/a²) construction time. Running the algorithm in (Eppstein et al., 2020) on this coreset, we obtain an alternative ((a)) apprrxxaiiiiii for k-CENTER in O(nk time.
In this paper, we present new trade-offs between approx- imation ratio and running time for k-CENTER. Specifi- cally, we focus on optimizing the trade-off in the case of = (0 < c < 1). Our results make a significant step forward towards the ultimate goal of achieving near-linear running time for approxxioiii in this regime.
Theorem 1.2. For every a 2 1, there exists an ((a)-
coresel of size k polylog(n) that can be computed in time O(nk2/a²) with probability at least 0.99.
Previously, it was observed that the point sequence dis- covered by an (approximate) furthest-neighbor traversal as in Gonzalez's algorithm (Gonzalez, 1985) is O(1)- coreset (Braverman et al., 2021), and one could use an algorithm in (Eppstein et al., 2020) to find such a se- quence, which yields an ((a)-coreset of size (kk in time (nn++/aa) While this coreset size is competitive, the run- ning time remains super-linear in k for k = n' (0 < c < 1), which is too large for our purpose of near-linear algorithms.
1.1. Our Results
We take a data reduction approach to systematically im- prove the running time of approximation algorithms for k-CENTER. Specifically, we use the notion of an a-coreser (for 2 1), defined as a subset S S P of the dataset P such that any 3-approximate solution to k- d-CENTER on S is an (a= + apaapproxnmation on the original dataset P.
Our main result consists of two coresets with slightly dif- ferent parameter trade-offs, both of size k o(n). This essentially reduces the input size from n to k- o(n), speed- ing up any (existing) approximation algorithm. Notably, obtain an ((1) apprrxxixinitononn in hear-linear time for k = n (0- < < 1). We summarize the new approxima- tion algorithms in Table 1.
Experiments. Our experiments validate the performance of our coresets, with a focus on Theorem 1.1, since The- orem 1.1 leads to near-linear running time for k- k-CENTER when k = n (0 < c < 1), which is likely to be prac- tical. Our experiments are conducted on four real-world datasets of various sizes and dimensions, and we evaluate the speedup of the well-known Gonzalez's 's algorithm (Gon- zalez, 1985) on our coreset. The experiments show that our coreset provides a consistently better tradeoff between the coreset size and clustering cost than baselines, and runs? 2 to times faster than directly running Gonzalez algorithm on the dataset, while still achieving comparable cost values.
Coresets. Our first result, Theorem 1.1, constructs an (a))-coreset of size Olkn2/a²))) in a runtime that is near-linear in n and independent of a. Running the exist- ing O(n'+1/a² )-time approxxmiiininooo algorithm (Epp- stein et al., 2020) on this coreset, we obtain an O(a)- approximation in time Ö(n+ 1-+1/0a2 n (11 This im- mediately improves the algorithm in (Eppstein et al., 2020). In particular, as long as h = nº (for any 0 < < 1) which can be arbitrarily close to linear n, this running time reduces to (n) by setting a = poly((1 - -))
1.2. Related Work
Our notion of coreset is related to the widely considered strong coreset (Agarwal et al., 2004; Har-Peled & Mazum- dar, 2004), which is a subset S C P satisfying that (S C) E (1 ++) cost (P,C) for all center sets C C Rd The key difference is that ours may not preserve the cost value on S for all C, but it does preserve the approxima- tion ratio. Moreover, this stronger notion inherently leads to a prohibitively large coresct size of (x)()) even for k = 1.4 Our notion is sometimes referred to as weak core- sets in the literature, and similar notions were also consid- ered in (Feldman et al., 2007; Munteanu & Schwiegelshohn, 2018; Huang et al., 2023; Carmel et al., 2025).
Theorem 1.1. For every 2 1, there exists an O(a)- coreset of size (akn)/a2")) that can be computed in time
Ö(n) with probability at least 0.99.
Our Theorem 1.1 relies on a geometrie hashing technique called consistent hashing (Czumaj et al., 2022) (see Defi- nition 3.1). Our main technical contribution is to devise new consistent hashing that offers a competitive parameter trade-off, while still running in poly(d) (d) time, exponentially improving the previous cxp(d) time construction (Czumaj et al., 2023) (albeit theirs achieves better parameter trade- offs). See Section 3 for more detailed discussion. This
"This lower bound is folklore, but be casily proved using an e-net on the unit sphere.
2

---

Faster Approximation Algorithms for k-Center via Data Reduction
Table I: Summary of approximation algorithms for k-CENTER in R2d
Approx, ratio
Running time
Reference
2
O(kkd) Ö(ntt1/a²)
Gonzalez (1985)
((a)
Eppstein et al. (2020)
((a)
Ö k2+1/a² 22 O(nkWaa)
Theorem 1.1 + Eppstein et al. (2020)
O(a)
Theorem 1.2 Eppstein et al. (2020)
2. Preliminaries
that any subset in Rd of diameter at most e/T intersects no more than A buckets (in expectation). Since consistent hashings are scale invariant in Rd, we omit the parameter in our discussion below. Ours and previous results are summarized in Table 2.
Notations. For m E Ng1, denote [m]] := m......m). For point set C S IRd let diam(C) denote the diameter of C. For x E R and r 2 0, the ball of radius r centered at x is denoted by B(x,r) r) = {y E R dist(x, (z. y) I r). and we write two sets A, B C Rd their Minkowski sum is A B := fo + y: E A. E B). For function f R= + R and set S S IRd, we define f(S) == {f(x) x S).
:= B(a,r) S for S C Rd. For
For every parameter B 2 1, Filtser (2024) constructed a deterministic consistent hashing (namely, the consistency guarantee is worst-case and not in expectation) with pa- rameters r = 3 and = O(d) exp(O(d/3)). However, computing ((x)) for a given point x requires both time and space that are exponential in d. Nevertheless, Filtser showed that this trade-off between I and A is tight up to second order terms regardless of runtime, even when the consis- tency guarantee is relaxed to expectation only (implicitly). Czumaj et al. (2023) constructed deterministic consistent hashing with the same parameters, requiring only ((f) space, though the function evaluation still takes exponential time in d. They also constructed time- and space-efficient consistent hashing, which can be evaluated in poly time but with sub-optimal parameters of A and I.
Definition 2.1 (Covering). Given a set P C IR and p p2000 0, a subset S _ P is called a p-covering for P if for every p E P. there exists a E S such that dist q) S p.
The following lemma will be useful in both of our coreset constructions. Its proof is deferred to Appendix A. Lemma 2.2 (Coarse approximation), There is an algorithu that, given as inpul a dataset P C I2 with |P| = n and an to the k-
integer k 2 1, computes a CENTER cost value with probability at least 1 1/ (nly(n),
running in time ((nd + polylog(n)).
Our hash function is the first to achieve the bound A exp(O(d/3))) (for some 0 < c < 1) when r = 33 for every B Z 1, while still running in polynomial time in d. Technically, we construct the hash function using a surpris- ingly simple randomly- grid, which is widely used in geometric algorithm design.
3. Efficient Consistent Hashing
The notion of consistent hashing was coined in (Czumaj et al., 2023), which partitions Rd into cells such that each small ball in Rd intersects only small number of cells. Partitions with similar properties have also been studied under the notion of sparse partitions for general metric spaces (see, e.g.. (Jia et al., 2005; Filtser, 2024)). The main differences are that consistent hashing requires the partition to be defined using a (data-oblivious) hash function and emphasizes computational efficiency.
Previous works also studied laminar consistent hashing (Busch et al., 2012; 2023), which is sequence of hash functions at different scales, each refining the previous one. We note also that Chen & Zhang (2016) studied a related notion consistent hashing, but their diameter guarantee was only probabilistic, so is not directly comparable.
Below we present our formal definition of consistent hash- ing, which relaxes the definition of Czumaj et al. (2023) by only requiring the number of intersecting cells to be bounded in expectation.
Lemma 3.2. For every B 2 22n and E. > there exists a (3, tg, -)-oosiisttnt hashing & .d + I2d with Lg := poly exp(O(d/33) /²)) which can be computed in (()) time.
Definition 3.1. A (T, A.onssonn hashing is a distri- bution over functions Φ R.d + Ed such that for every Rdd.
Proof. Since it suffices to define the hash function for an (arbitrary) fixed E, in this proof we fix E == vd.
(diameter) diam (p- 1 (x)) < l, and (consistency) E[( B (z, f)]] S A.
The hash is defined by a randomly-shifted grid. Formally, we first choose a uniformly random vector e E [0, 1]d and, for each x Rd. define (p(x) = [x +
Construction.
In this definition, the hash partitions Rd into buckets of diameter at most é (which can be picked arbitrarily), such
3

---

Faster Approximation Algorithms for k-Center via Data Reduction
Table 2: Summary of results on consistent hashing in Euclidean R..
The third result is a lower bound.
T
A
Guarantee
Runtime
Space
Reference
exp(O(d))
worst-case
exp(d)
exp(d)
Jia et al. (2005)
8
(dd exp((((/3)
worst-case
exp(d)
exp(d)
Filtser (2024)
8
A A> +))
expected (implicit)
N/A
N/A
Filtser (2024)
8
((d) exp(O(d/3) ((d)
worst-case
exp(d)
poly(d)
Czumaj al. (2023)
(dd--5
worst-case
poly(d)
poly(d)
Czumaj et al. (2023)
B
poly(d) exp (x((3()))))
expected
((d)
O(d)
Lemma 3.2
w/. Here, for a vector (21,..., za) E IR4, we define [=] = [22)..,,.....,..............,.., [za]) E RR, i.e, rounding down z coordinatewise.
Applying Lemma 3.3 with our
= Vd/B. we have
vol (Cuais) S poly(d) exp
3
(2 (2m) (Va/3)
2
3
(2x) bd/38
Analysis. To evaluate sf()), we simply round æ + down coordinatewise to the nearest integer, which takes O(d) time. The diameter property is also straightforward, since sp- (t) = x ve 0 + 1) (t 24), which is half-open unit cube and has diameter vd= = E.
= poly(d) exp
2
= poly(d) exp (O(d/38)
Therefore.
It remains to verify that an arbitrary ball of radius r = vd/3 intersects only poly(d) exp(O(d/3$ grid cells in expectation. Let E Idd arbitrary and consider the ball rx) Let f = [r]. By symmetry, we can assume w.l.o.g. that x E [F, F 1)d Further, for the sake of analysis only, we will slightly change the hash function. Let A >> F be some fixed large integer to be determined later. Instead of sampling E [0, 1jd, we sample = (ei...., va) E [0, A] uniformly at random and map each point to ly + w]. Note that the number of intersecting grid cells by a ball centered (x + v) equals the number of intersecting cells by ball centered at x + (v) mod I,..., va mod 1). Thus, the two hash functions have exactly the same expected consistency.
Iz + + B(ū,r) EXx (+) vol (tt - 2z,t, [
vol (0, A)4)
vol (C,) Ad Ad poly(d) exp(O(d/3i))
Here (+) an inequality, rather than equality. because the Minkowski sum [t, x; 4 F, + +1) @ B(ū, r) might not be fully contained in [0, Ajd. Only grid cells from G = [0, A + 3F] have a non-zero probability of intersect- ing B(x v.r). Since there are only (A + +3r) such grid cells K, by linearity of expectation, the expected number of grid cells intersecting B(x + v, is at most
(A + / poly(d) exp(O(d/3ã)) -ooly(d) exp(O(d/3i))
Since x E 1)d and v E [0, AJd, the ball B(r + r. can only intersect grid cells in the box G [0, + 37)". Fix some grid cell K = x [t, 4 + 1) C G. Let Xx be an indicator for the event that the ball B(x+ v) intersects K. This happens if and only if the ball B r) intersects the box [t, Z4, 4 - 2, + 1), or, V is contained in the Minkowski sum of the box x [t+ F,, 2, + 1) and the ball r)) The following lemma bounds the volume of this Minkowski sum.
where the last equality holds for large enough A. This verifies the consistency bound of the consistent hashing and completes the proof of Lemma 3.2.
4. Proof of Theorem 1.1
We prove Theorem 1.1 in this section (restated below). Theorem 1.1. For every a 2 1, there exists an O(a)) coresel of size O(kn2/a2/3 that can be computed in time Ö(n) with probability at least 0.99.
Lemma 3.3 (Aiger et al. (2014), Lemma 3.1). Let C =
[0, 1]dd be the unit cube in Rd and 0 < r S / /d/2m be a parameter. Let C, C + B(õ,r) then
We start by reducing the task of finding coresets to the con- struction of p-coverings (see Definition 2.1) 1) via a standard fact that any a-approximation on an (po))-ccovering is (a + appppoxoxnn to CENTER (see Lemma 4. 4.1);
vol (C.) S (d) exp (3/2 (2x) (

---

Faster Approximation Algorithms for k-Center via Data Reduction
hence, suffices to find small (8 (oooe-cg as core- set. Indeed, covering is a fundamental notion in geometric optimization. In the context of k-CENTER, it can be viewed as bi-criteria approximation that uses slightly more than k center points.
for all 2; P. Moreover, the image S(P) can be computed in O n) time with probability at least 1- 1-1ppolymm)
Now we are ready conclude the proof of Theorem 1.1.
Lemma 4.1. For a dataset P C Rdd and integer k. consider a (3 -covering S C P for some 3 2 1. Then any a- approximation on S is an (a + p)paprooimotooon on P for k-CENTER. In other words, S is a 3-coreset.
Proof of Theorem I.I. For a generic point set W C Re, let opt(W) be the optimal k-CENTER value on W. The algorithm for Theorem 1.1 goes as follows. We first run Lemma 4.3 with some constant e = 0(1) to obtain a map- ping f R + Rd where d' O(log n). Let P := f(P) be the dataset in the target space after JL. Then, we ap- ply Lemma 4.2 on P', to obtain an O(a opt((")) S' C P' of P'. Let S == (S'), and this is well-defined since S' is a subset of P' and f is injective on P. The algorithm returns S as the covering.
Proof. For a generic point set W S Rd and a point x E Rd, we define the projection function Tw Tw(x) (x) == argmingew dist(z, y). which maps x to its nearest neigh- bor in W (ties are broken arbitrarily). Since S is (3 opt)- covering, for every E P we have dist(p, (p)) S opt. Let C be an a-approximation k- K-CENTER S. Then,
The running time follows immediately from Lemmas 4.2 and 4.3. Next, we verify that S is desired covering. Condi- tioning on the success of Lemma 4.3, i.e., for every 2; P. (xst(f f()) e (1 dist(2, y). consider arbi- trary x E P. Then
cost Cost(P,,C = max (pst ( pEP
max (ist(y, sp))) + (()((rs())))((sss)) PEP
max (ist(piistsspppo.. Ts(p) + max dist (p))) PEr
PES
I B opt to opts
dist(ar, S) < (1 c)) dist(J(x),, S*)
I opt +o opt,
$ (1+ (p
$ 2(1 + +c)
where the last inequality follows from the fact that the opti- mal k-CENTER cost on the subset S cannot be larger than the optimal k-CENTER cost on P. which is true since we consider the continuous version of the k- k-CENTER problem where centers are chosen from the entire Rd
s O(a) opt(P),
where the first inequality directly follows from the condi- tioned event, and the third inequality from the claim that opt(P") I 2(1 + e) opt(P), which can be derived from the conditioned event as follows'. Consider 2-approximation Č C P of k-CENTER on P (for instance, consider the solu- tion of Gonzalez's 's algorithm (Gonzalez, 1985)), and the con- dition implics PPt( < cost(P', f(C) < 2(1 + e) opt. Finally, the failure probability follows from a union bound of the failure of Lemmas 4.2 and 4.3. This finishes the proof.
Thanks to Lemma 4.1, remains to find a small opt)- covering. We give the following construction of covering based on consistent hashing (Definition 3.1). This is the main technical lemma for Theorem 1.1. Its proof is post- poned to Section 4.1.
Lemma 4.2. There is an algorithm that takes as input dataset P C Id with [P| = n, 3 2 1 and integer l > 1, computes a set S [ P with [S] S k -poyydd) exp(d/ 32/3) in time Ond n), such that S is an Opt coverring of P with probubility at least 0.991.
4.1. Proof of Lemma 4.2
Proof overview. The covering construction is based on consistent hashing (see Definition 3.1). Consider the k clusters Cj .i...., Ct in an optimal solution, then by def- inition U.C: = P and diam(C?) S 2opt for all C, Roughly speaking, the key property of a consistent hash- ing s. is that each C; is mapped to |(p(C;) < A dis- tinct buckets, and that each bucket has diameter opt), where A is a parameter of the hashing and we have A poly(d) (d((3)))))) in our construction (Lemma 3.2). Then, picking arbitrary point from every non-empty bucket yields an
Lemma 4.2 allows us to compute a covering set whose size is exponential in the dimension (assuming d > 8). To mitigate this, we apply the Johnson-Lindenstnn transform (Johnson & Lindenstrauss, 1984), using random projections to reduce the dimension of the input point set to O(logn). n). The JL Lemma is restated as follows. Lemma 4.3 Johnson-LLindenstran be a set of n. points and e E (0, 1)) Then there exists a map P Rd for some d' = =(E log n) such that
(JL.
Lemma). Let P C Rdd
of size kA. This hash $In fact, one can show opt(P") + opt(P). which has also heen analyzed in, e.g., (Jiang et al., 2024).
(1 disitts, v) S dist(f(x), f(v)) S (1 + dist
5

---

Faster Approximation Algorithms for k-Center via Data Reduction
Algorithm 1 Covering based on consistent hashing
opt around st's, i.e., P = - Bplc, opt). As os S. by linearity of expectation, it holds that
1: apx f- 7-approximate of k k-CENTER(P) using
Lemma 2.2, where 7 = poly(n).
A p
2: io f poly(d) exp(O(d/ (as in Lemma 3.2)
E ||S = E 11p- (P) = E
Bp (r(c)
3: for i = to [log>l do
j=l
4: T - _px 2'
5: let fr be a (3, tg, BT) hashing sampled using
E p1 (Bp(( opt))[] s k tt
Lemma 3.2
6: for each = E pr (P), pick an arbitrary representative point r2) from the bucket 0-'(2) P
By Markov's inequality, Pr[[S,| > 200kt,] - 0.005.
7: let S, + frep(z) & E (P))
Proof of Lemma 4.2. We define the two following events:
8: if [f|s]| S 200kt, then return S,
9:
end for
Eapx: the event that the k-CENTER approximation al- gorithm in Lemma 2.2 succeeds: opt S apx $ Y opt.
Ehash: the event that for r such that opt S T < 2 opt. it holds that [S+] S 200kt..
is data-oblivious and we can evaluate xo(x) for every x E Idd in (dd) time, which leads to a (n) running time of Lemma 4.2.
By Lemma 2.2 and Lemma 4.5, with probability at least 0.991, events Eapx and Enshh both happen. We now condi- tion on both events and, in the rest of the proof, argue that the algorithm succeeds. Lemma 4.2 will then follow.
Algorithm. The algorithm is listed in Algorithm 1. Let opt denote the cost of the optimal solution to the k- CENTER on P. The algorithm starts by finding a poly(n)- approximation to opt (using Lemma 2.2). then checks n) geometrically increasing values of T, one of which estimates opt up to factor of 2. For each value 7, we pick consistent hash yor in Lemma 3.2, with scale parameter 3.7, such that the points of every ball of radius 8-r "3 are (d/ cells in
Covering property. The algorithm iterates over different values of т, starting at To in jumps of 2, with the maximum value being Tlog >] apx 2 [lo >1 2 apx 2 opt. Let r' be the estimate such that opt T' < optt. If the algorithm will reach the estimate T', then as we conditioned on &nash, the algorithm will halt and return S,,, Otherwise, the algorithm will halt earlier at some value S - S opt. In either case, by Lemma 4.4, the algorithm returns a set S,, which is (BT) (ovvrring for P. Note that 3T < 2/3 opt.
apx S opt, and increase
7
hashed into only fg- = poly(d) expectation. For each hash ypy, the algorithm computes a set S,, containing single representative from every nonempty hash cell. Once |S,| 10k 1g, the algorithm halts and returns S,.
Consider an estimate J such that < opt < r. The points in P are contained in k balls of radius opt < + (around the centers in the optimal solution). Under yr, the points within each of these balls are hashed into only lg cells ex- pectation. This implies that, with high constant probability, [S+| S 200k tg. leading the algorithm halt and return S,. We now proceed with formal proof.
Running time. The invocation of Lemma 2.2 in Line I only takes O(nd + n log n) time. The for-loop runs at most (log times, and in each iteration, it takes ((nd) time to evaluate all hash values (PP). In summary, the overall running time of the algorithm is (nd n.. This finishes the proof of Lemma 4.2.
Lemma 4.4. For every T, the set S. is (8r)-covering for P (with probability 1).
5. Constructing Covering via Sampling
We now prove Theorem 1.2 (restated below).
Theorem 1.2. For every a 2 1, there exists an O(a)) coresel of size k polylog(n) that can be computed in time ((nk with probability at least 0.99.
Proof. Clearly, S, C P. Now, fix some p E P, let x == (p). Then rep(2) Sr, and by Definition 3.1, we have dist(p, S,) S rep(()) I di, (x)) S BT. This verifies the definition of 3 -ooveiiin
The proof similar to that of Theorem 1.1, using reduction to covering (Lemma 4.1). Hence, the remaining step is to find suitable covering for Theorem 1.2, which is stated in the following lemma. The lemma relies on an approximate nearest neighbor search (ANN) structure, where given a set of input points and a query point g. the ANANN finds for each a point x E T such that dist(r, 4) S a dist(g. T).
Lemma 4.5. For T 2 opt, |S+| < 200kt, with probability at least 0.995 (over the randomness sr).
Proof. Let C* = (ci, } be an optimal solution for k-CENTER, Then P can be covered by the balls of radius
6

---

Faster Approximation Algorithms for k-Center via Data Reduction
Lemma 5.1. Given a set of points P C R2, and k; 3 2 1, there is an algorithm that runs in ) time, and with probability at least 0.991 returns set S S P of k. (olylog(n) points such that S is an ((3opt))-overize of P.
Algorithm 2 Covering based on sampling
1: apx < a 7-approximate of k- k-CENTER(P) using
Lemma 2.2, where ? poly(n)
2: for i + to [log 7 do
3: + apx 2 S. + 0. Q c P
Note that Theorem 1.2 follows directly from Lemmas 4.1 and 5.1. The rest of this section proves Lemma 5.1.
for j 1 to L = 5[log ni do
5: draw Olloogn) uniform samples 80) with re- placement from Q(--1)
Proof overview for Lemma 5.1. Our proof is based on random hitting sets. For the sake of presentation, assume that the k clusters in an optimal solution are of similar (). Then a uniform sample S of size Olk log n) would hit all clusters w.h.p. Furthermore, by the definition of B-CENTER, the entire dataset is contained in (2 opt)- neighborhood of S. This (2 neighboooooo of S gives the covering and can be computed using ANN. The general case where the clusters are not balanced can be handled similarly. Specifically, for a random sample S of O log n) points, at least half of the points will, with high probability, be within a distance of 2 opt from S. We can eliminate these points, and repeat this process for (log n) rounds to cover all points.
6:
for each x E Q(i-1), compute dist(a, Sti) such that (iiit(zz,5() 2 3 dist(a, ,()) using ANN R6) + {i E Qú-1); disi Súi) < 233r}
7:
size (()).
8:
S, + S()) Qúi + Q(i-)) \ RQ6)
9:
if if = 0 then return S,
10: end for
11:
end for
Table 3: Specifications of datasets, where d is the original data dimension and d' is the target dimension of the JL transform.
dataset
size (approx.)
d
d'
Kddeup
5M
38
30
Covertype
581K
55
50
Census
2M
69
60
Algorithm. The algorithm (Algorithm 2) begins by com- puting a poly(n)- approximaaiio to opt, denoted by apx. Then it checks (llg n) geometrically increasing values of T, one of which estimates opt up to a factor of 2. For each value of T, the algorithm attempts to construct a coreset S,, such that for every point E P. dist(z, S,) S 23T. In more detail, a set Q of uncovered points is maintained. The process consists of L- = O(log n)) iterations, where in each iteration, Ol log n) random (uncovered) points from Q are added to S,. ANN is then invoked at Line 6, using the newly sampled points as the input set and the uncovered points in Q as queries, where we use the ANN algorithm of Andoni & Indyk (2006). Every point whose 3-approximate nearest neighbor is within a distance of at most 2,37 is subsequently removed from Q. If Q becomes empty during the O(log n) iterations, the algorithm returns S,.
Fashion-MNIST
70K
784
100
Line 9.
Proof of Lemma 5.1. During the execution of the algorithm we construct an 8-ANN structure Ollog n) times, each with input size O(k log n)). On each such data structure we perform at most queries. Specifically, we use the B-ANN algorithm of Andoni & Indyk (2006), which takes Ô Õm (ml+11/5 +1/32) pre- pre-processing time and Ö(m 1/3²) query time to compute an ((3)- approximate NN for each query point in Rd, over an m-point input set. This algorithm answers all (n)) queries successfully with 1 1- -1/ p/lyy() probability. Hence, the overall running time is Ö(n k2/0²) (where we set m = O logg)) This also dominates all the other steps.
For the analysis, consider T 2 opt, and Q S P. Since Q can be covered by l balls of radius r, by an averaging argu- ment, least half of the points in Q must belong the balls that each contains at least zे fraction of Q. Consequently, each such point will, with constant probability, be within a distance of at most 27 from the sampled points and will thus be removed from Q. It follows that Q is expected to shrink in size by constant factor each iteration and, after Olog n) iterations, becomes empty. The running time is dominated by the executions of ANNs. The next lemma is the main technical guarantee of Algorithm 2 and its proof is postponed to Appendix B.
Let E [0, [log be such that aax 2 < opt - AEX 22, If the algorithm terminates at iteration i' < i, then it has found a set S, which is a p-covering of P for = 2,3 apx
7
2''1 < 2,3 opt, as claimed. Otherwise, by Lemma 5.2, with probability at least - 1/n, Algorithm 2 would termi- nate at the i-th iteration and, in this case, S, is a p-covering of P for p 23 apx 2 < 2,3 2opt = 4,3 opt.
6. Experiments
We implement our coreset from Theorem 1.1 and evaluate its performance by measuring how effective speeds up the classical algorithm of Gonzalez (1985), which gives a
Lemma 5.2. Suppose that T 2 opt. With probability at least 1/n, there exists j S L. such that QU) = at
7

---

Faster Approximation Algorithms for k-Center via Data Reduction
ours
benchmark
uniform
low-dim
k-median
tree-embedding Tashion-MNIST
Kddcup
Covertype
Census
20+00
3000
3000
2500
000
1000
Co5
2000.0
(00
5500
1500.
1000.
200.0
500
2000
2400
0.0
6226
1200
200
10000
12030
2000
4320
0003
10000
13820
35200
2033 19000
2003 50000 0000
1000
4000
(000
I200
10335
Coreset Size
Coreset Size
Coreset Size
Coreset Size
Figure 1: The cost evaluation for all baselines in each dataset.
Kddcup
Covertype
Census
Fashion-MNIst
1000
6200
090
5000
2000
800
Cost
600
600
.00
1000
3000
200
3000
500
4520
4000
10000
2200
2000
0003
6000
2000
30500
12000
1:000
20000 sc0on 40000 50000 6000
P2000
6000
4500
4000
10000
Coreset Size
Coreset
Coreset
Figure 2: The variance evaluation for our coresct.
2- 2-approximation for k- d-CENTER. We focus on the coreset of Theorem 1.1 due to its near-linear running time and use of simple grid structure, which makes it more practical. Specif- ically, we conduct experiments with varying coreset sizes and report running time and the corresponding clustering cost when running Gonzalez's 'sssi algorithm the coreset. The research code for this experiment is available at GitHub repository.
Baselines, We employ five baselines for k- A-CENTER, one is brute-force benchmark, three are based, and the other one is based on tree embedding method. The brute- force benchmark, named benchma rk, runs Gonzalez's algorithm on the entire dataset. The three baseline coresets are as follows: a) heuristic coreset based uniform sam- pling, called uni form, which samples uniformly a subset of a given size from the dataset; b) a coreset designed for low dimensions, called fow-dim, which has worst-case size of (I:20(d) (Agarwal et al., 2004); c) a coreset designed for k-MEDIAN clustering, called k-median (Chen, 2009; Cohen-Addad et al., 2021). We run Gonzalez's algorithm on the coresets. The last baseline is based on tree embed- ding, where first run fast tree embedding algorithm via randomly-shifted grid (Indyk, 2004), which has O(log" n) distortion, followed by running Gonzalez's 's algorithm on the tree embedding, referred to as rrree-embedding
Datasets. We use four real datasets: Kddcup (Stolfo et al., 1999), Covertype (Blackard, 1998), Census (Meek al., 2001), and Mashion-MNIST (Xiao et al., 2017). For each dataset, we extract numerical features to construct vec- tor in Rd for each record, and we perform a Johnson- Lindenstrauss (JL) transform on each dataset. The detailed dataset specifications as well as the target dimension of the JL transform are summarized in Table
Note that there no standard way to adapt the low-dim im construction to our context; a naive implementation can lead easily to coreset size close to Okk204)), which is prohibitively large for our datasets. In experiments, we implement this 1ow-dim baseline in manner similar to our coreset construction, with the only difference being that we do not use a random shift in the hash function.
Implementation details. The implementation of our core- set mostly follows Algorithm 1 but involves an important modification. Since our experiment is to generate coreset with specified size budget (instead of pre-defined target error), the error parameter 3, which controls the coreset size, is no longer useful. Consequently, we replace the coreset size upper bound 10kL, in Line 8 directly with the budget s. We also replace the third parameter L = .T of the hash function in Line 5 with r. The coresets generated in this manner may not have an exact size of s, but it is nonetheless close to s.
Experiment setup. For all experiments, we set the num- ber of centers k & vn, where n denotes the size of the dataset. For coreset baselines, we vary the target coreset size s (ranging from up to 30k), compute each baseline coresct with the target size s, and evaluate the clustering cost on the full dataset. We report both the running time
8

---

Faster Approximation Algorithms for k-Center via Data Reduction
ours
benchmark
uniform
low-dim
k-median
tree-embedding
kddcup
Covertype
Census
Sishion-MNIST
Running lime (seconds)
Running (seconds)
Running lime (seconds)
-00
Running Time (seconds)
100
30
3300
1000
2025
1000
30000
12003
3530
1000
0033
2200
10300
35000
10003
30000 10000 20333 30200 20000
3005
1000
0935
1000
10000
Coreset Size
Coreset Size
Coreset Size
Coreset Size
Figure 3: The running time evaluation for all baselines in each dataset.
and the evaluated cost, averaged over 3 independent trials. All algorithms are implemented in C++ and compiled with Apple Clang version 15.0.0 at -O3 optimization level. All the experiments are run on MacBook Air 15.3 with an Ap- ple M3 chip (8 cores, 2.22 GHz), 16GB RAM, and macOS 14.4.1 (23E224).
maximum distance is critical.
We also report the variance of our algorithm in Figure 2, which is very small compared to the magnitude of the cost. Finally, we report in Figure 3 the running time, including both coresct construction and the execution of Gonzalez's s algorithm, as function of coreset size. Ours yields 2x 4x speedup over benchmark, and has generally comparable running time with other baselines albeit achieving better accuracy discussed above.
Experiment results. We depict in Figure 1 the clustering cost of the baselines. More specifically, this also shows a trade-off between the coreset size and the clustering cost for coreset baselines (and for non-coreset baselines benchmark and tree- eree-embb we simply plot their cost constant function of size). Our coreset uses 5% of the full dataset to achieve < 1.3 times of benchmark costs on all datasets. Moreover, our algorithm consis- tently achieves the smallest cost compared with the other uni rom, low-dim and tree-embeddie dding baselines, and outperforms x-median baseline on most datasets, which confirms the superior performance of our coresets.
A Akknowledgements
The authors would like to thank the organizers of the "Mas- sive Data Models and Computational Geometry" workshop at the University of Bonn, where the initial discussions lead- ing to this paper took place. Arnold Filtser was supported by the Israel Science Foundation (grant No. 1042/22). Yi Li is supported in part by Singapore Ministry of Education AcRF Ioannis Psarros has
Tier 2 grant MOE- been partially supported by project MIS 5154714 of the Na- tional Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program. Qin Zhang is partly supported by NSF CCF-1844234
We give more discussions on the performance of baselines. The uni form baseline performs generally worse than ours and low-dim (albeit comparable to low-dim in Cover- type), which is expected, since na've uniform sampling may not hit sparse clusters. This is particularly seen in Kddcup dataset, where it has been observed that this dataset has out- lier/noisy points (Tavallace al., 2009). The performance of 1 cwwdim is closer ours, which is an interesting fact, since our implementation helps it to escape the worst-case size of k (d) on the tested datasets. As mentioned, the only difference between the implementation of Low-dim and ours lies in whether or not random shift is applied in hash function (Lemma 3.2). Therefore, the performance gain of ours justifies the effectiveness of random shift even on real-world datasets. The k media baseline achieves lower costs Covertype. This suggests that the solutions to k-MEDIAN and k- CENTER are similar on this dataset. The tree- trree-embedding baseline performs poorly across all datasets. this due to the fact that the tree embedding method only provides bounded distortion in expectation, which is insufficient for the -- CENTER objective, where the
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. We do not see any immediate socictal consequences of our work.
References
Agarwal, P. K., Har-Peled, S., and Varadarajan, K. R. Ap- proximating extent measures of points. J. ACM, 51()): 606-635, 2004.
Aiger, D., Kaplan, H., and Sharir. M. Reporting neighbors in high-dimensional euclidean space. SIAM Journal on Computing, 43(4):1363-133 1395, 2014.
Andoni, and Indyk, P. Near-optimal hashing algorithms

---

Faster Approximation Algorithms for k-Center via Data Reduction
for approximate nearest neighbor in high dimensions. In FOCS, pp. 459-468 TEEE Computer Society, 2006.
2204.02095,, URL htwp::ttt////ectc :/tp::://d....// org/10 org.11.4455000 48550/ arXiv. 02095. see also conference version in FOCS22.
Avarikioti, Z., Emiris, Z., Kavouras, L., and Psarros, High-dimensional approximate r-nets. Algorithmica, 82 (6):1675-1702, 2020.
Czumaj, A., Gao, G., Jiang, H., Krauthgamer, R., and Veselý, Fully-scalable MPC algorithms for clustering in high dimension. In ICALP, volume 297 of LiPles, pp. 50:1-50:20. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2024.
Balcan, M., Ehrlich, S., and Liang Y. Distributed k- means and k-median clustering on general communica- tion topologies. In NIPS, pp. 1995-2003, 2013.
Dong. X.
L. and Naumann, Data fusion: resolving data conflicts for integration. Proceedings of the VLDB En- dowment, 2(2):1654-1655 2009.
Bateni, M., Esfandiari, H., Fischer, M., and Mirrokni, V. Extreme k-center clustering. In AAAI, pp. 3941-3949.
AAAI Press, 2021.
Ene, A., Im, S., and Moseley, Fast clustering using mapreduce. KDD, pp. 681-689. ACM, 2011.
Blackard, J. Covertype. UCI Machine Learning Repository, 1998. DOI: http:://bb.orrg11.224322/000
Eppstein, D., Har-Peled, S., and Sidiropoulos, A. Approxi- mate greedy clustering and distance selection for graph metrics. Comput. Geom., 11(1):629-652, 2020.
Braverman, V., Jiang, S. H., Krauthgamer, R., and Wu, X. Coresets for clustering with missing values. In NeurlPS, pp. 17360-17376 2021.
Feder, T. and Greene, D. H. Optimal algorithms for approx- imate clustering, In STOC, 434 444. ACM, 1988.
Busch, C., Dutta, C., Radhakrishnan, J., Rajaraman, R., and Srivathsan, S. Split and join: Strong partitions and universal steiner trees for graphs. In FOCS, pp. 81-90. IEEE Computer Society, 2012.
Feldman, D., Monemizadeh, M., and Sohler, C. A PTAS for k-means clustering based on weak coresets. In SoCG, pp. 11-18. ACM, 2007.
Busch, C., Chen, D. Q.. Filtser, A., Hathcock, D., Her- shkowitz, D. E., and Rajaraman, One tree to rule them all: holy-logarithmic universal steiner tree. In FOCS, pp. 60-76. IEEE, 2023.
Filtser, A. Scattering and sparse partitions, and their appli- cations. ACM Trans. Algorithms, (YY4):3:1-30:4:) 2024. See also conference version in ICALP20.
Carmel, A., Guo, C., Jiang, H., and Krauthgamer, R. Coresets for 1-center in & metries. In ITCS, 2025.
Gonzalez, T. F. Clustering to minimize the maximum in- tercluster distance. Theor Comput. Sci., 38:293-306, 1985.
Chen, D. and Zhang. Q Streaming algorithms for robust distinct elements. In SIGMOD Conference, pp. 1433- 1447. ACM, 2016.
Mar-Peled, S. and Mazumdar, S. On coresets for k-means and k-median clustering, In STOC, pp. 291-300. ACM, 2004.
Chen, K. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923- 927-947, 2009.
Har-Peleds S., Indyk, P., and Sidiropoulos, A. Euclidean spanners in high dimensions. In SODA, pp. 804-809, SIAM, 2013.
Cohen-Addad, V., Saulpic, D., and Schwiegelshohn, C. A coreset framework for clustering. In STOC, pp. 169- 182. ACM, 2021.
Henzinger, M. and Kale, S. Fully-dynamic coresets. In ESA, volume 173 of LIPIcs, pp. 57:1-57:21. Schloss Dagstuhl Leibniz--Zetrum für Informatik, 2020.
Coy, S., Czumaj, A., and Mishra, G. On parallel k-center clustering. SPAA, pp. 65-75. ACM, 2023.
Herzog, T. N., Scheuren, J.J., and Winkler, W. E. Data qual- ity and record linkage techniques, volume 1. Springer, 2007.
Czumaj, A., Jiang, S. H., Krauthgamer, R., Vesely, P., and Yang, M. Streaming facility location in high dimension via geometric hashing. In FOCS, pp. 450-461. JEEE, 2022.
Hochbaum, D. S. and Shmoys, D. B. A best possible heuris- tie for the k-center problem. Math. Oper. Res., 10(2): 180-184, 1985.
Czumaj, A., Filtser, A., Jiang, S. H., Krauthgamer, R., Vesely, P., and Yang, M. Streaming facility loca- tion in high dimension via new geometric hashing. CoRR, abs/2204.02099 2023. doi: 10.48550/ARRIV.
Hochbaum, D. S. and Shmoys, D. B. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 33(3):533-550, 1986.
10

---

Faster Approximation Algorithms for k-Center via Data Reduction
Huang, L., Jiang, S. H., and J. The power of uniform sampling for k-median. In ICMI,, volume 202 of Proceed- ings of Machine Learning Research, pp. 13933-13956. PMLR. 2023.
Thorup, M. Quick k-median, k-center, and facility location for sparse graphs. SIAM J. Comput. 34(2):405-433 432, 2004.
Vershynin, R. High-Dimensional Probability: An Intro- duction with Applications in Data Science. Cambridge University Press, 2018.
Indyk, P. Algorithms for dynamic geometric problems over data streams. In Babai, L. (ed.), Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, II, USA, June 13-16, 2004, pp. 373-380. ACM, 2004. doi: 10.1 00.114//0007352.00074133 URL https: //doi orr.i.org.oooooo
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
11 4.5 4 007413.
Jégou, H., Douze, M., and Schmid, C. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 1371)2117-128, 2011.
Jia, L., Lin, G., Noubir, G., Rajaraman, R., and Sundaram, R. Universal approximations for isp, steiner tree, and set cover. In STOC, pp. 386 386-395. ACM, 2005.
Jiang, S. H., Krauthgamer, R., and Sapir, Moderate dimension reduction for k-center clustering. SoCG, volume 293 of LIPIcs, pp. 64:1-64:16. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2024.
Johnson, and Lindenstrauss, J. Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics, 26: 16:189-206 206, 01 1984. doi: 10.1090/comm/026/7744000.
Koudas, N., Sarawagi, S., and Srivastava, D. Record linkage: similarity measures and algorithms. In SIGMOD, pp. 802- 803. ACM, 2006.
la Tour, M. D. and Saulpic, D. Almost-linear time approx- imation algorithm to euclidean k-median and k-means. CoRR, abs/2407. 1217, 2024.
Meek, C., Thiesson, B., and Heckerman, D. US Census Data (1990). UCI Machine Learning Repository, 2001. DOI: http:///b..ongg/0.2233/////
Megiddo, N. and Tamir, A. New results the complexity of p-center problems. SIAM J. Comput., 12(4):751-758, 1983.
Munteanu, A. and Schwiegelshohn, C. moresets-methods and history: A theoreticians design pattern for approxi- mation and streaming algorithms. Künstliche Intell., 32 (1):37-53, 2018.
Stolfo, S., Fan, W., Lee, W., Prodromidis, A., and Chan, P. KDD Cup 1999 Data. UCI Machine Learning Repository, 1999. DOI:
Tavallaee, M., Bagheri, E., Lu, W., and Ghorbani, A. A. A detailed analysis of the kdd cup 99 data set. In 2009 IEEE symposium on computational intelligence for security and defense applications. pp. 1-6. IEEE, 2009. doi: 10.1 NADDA..00.5535660

---

Faster Approximation Algorithms for k-Center via Data Reduction
A. Proof of Lemma 2.2
Lemma 2.2 (Coarse approximation), There is an algorithm that, given as input a dataset P IR with [P| = n and an integer k L, computes a poly(n))-pproxime))) -approximation the k- E-CENTER cost value with probability at least 1 1/ poly(n). running in time O(nd n polylog(n)).
Proof. The plan is first do random projection ID, and show that the pairwise distance is preserved up to poly (n) factor. This step takes ((nd) time. Then k-CENTER on ID (Megiddo & Tamir, 1983).
apply off-the-shelf near-linear polylog(n) time algorithm for
Specifically, let u E R be a random vector with entries sampled independently from a standard Gaussian distribution, i.c., V ~ NO, Ia). For every point in P. compute its inner product with v, resulting in P', i.e., P = {p, v) Vp E P). P can be interpreted as the projection P onto one-dimension. remains to prove the following distortion bound.
Claim. Vr, P.
dist(r.y)) poly(n)
s ((v, (v, v) x dist(x. poly(n) 2 1 11-1/1 1-ppynn()).
Proof of Claim. The claim trivially holds if y. and hence assume * y. Let == ((v,2) (v, v)) dist(x, y). Then by standard property of Gaussian,
_N 1). On the one hand, by Markov's inequality, we immediately obtain Pr[[u] 2 poly(n)] & 1/ //poly(n) since E[[u|] = ((1). On the other hand, since the density function of N 1) is upper bounded by 1/v2i, we know that Pr[[w] < // poly(n)] S 1/ poly(n) by integrating the density function from -1/ (nly(n) to 1/ poly(n). This finishes the proof.
B. Proof of Lemma 5.2
Lemma 5.2. Suppose that opt. With probability at least 1 1/n, there exists j S. L such that Q = 0 at Line 9.
Proof. Fix some iteration j in the inner for-loop (Line 4). We claim that
Pr [100) < 106-01
That is. in any given iteration, the size of Q decreases by factor of at least 2 with probability at least 3.2 Over the L iterations of the for-loop, if this size reduction occurs in at least log n iterations, then Q(') will be the empty set for some j' & L. Assuming that inequality (1) holds, the probability that the size reduction occurs less than log n times is negligibly small:
Pr Q(4)) + =0]
log
(+)
L.e
[log n.
26
21
[log nz
==0
(5c)
[oam]]
32 flog
2 [log n]
where (+) follows from the bound Ei= (*) S (en k (see, e.g., Exercise 0.0.5 in Vershynin (2018)).
remains to prove inequality (I). Let tci,..., . be an optimal solution for k-CENTER on P. thus Qύ-1) C C U Br(c,, opt). Let C1, C2...., Ck be a partition of Q(i-1) such that Cg S Br(c, opt) for all g E [k.]. In particular, [Q/511) and small otherwise. Denote by C the (Q0-1) (Q4- - Let v the event 2k
diam(C,) I 2 opt for each Cy- We say that cluster Cg large if Cgyl 2 set of large clusters. Note that the number of points in small clusters is at most k
24
that the set g6i of samples contains at least one point from each large cluster. By a union bound, the probability that does not happen
Pr V
Pr 3 large cluster C₂ s.t. Cg ((5))
12

---

Faster Approximation Algorithms for k-Center via Data Reduction
Σ
Pr C.
( =
CGEC
(1
Olk-log n)
Σ CGEC
Q
O(k-logn)
k 1 n 0(1)
k. 1
2k
Next, condition on V. Then gGi contains a point from Cg for every large cluster C.- Since each cluster has diameter at most opt and more than half of the points belong to large clusters, it follows that there are at least 1@ points in Q(i-1), each of which is within a distance of at most 2opt I 2T from some point in 5ú) Our ANN will return with high probability, for each E Q estimate dist(z,, (()) such that dist(ar, ((5))) I B (di (())). It follows that dist(x, (()) < 23T for all the large cluster points. Consequently, all these points will be included RO) and thus [Q0) = (Q0-1) \ R -6- with probability at least z. as claimed.
C. Composability and Reducibility of Covering
Note that our a-coresets in both Theorem 1.1 and Theorem 1.2 for point set P are specifically (p for P. We show that such covering is both composable and reducible, in the following claims. Combining both claims, our coreset may be plugged in a merge-and-res -eduucdcceee framework HHar-Peled & Mazumdar, 2004), which has been used to obtain streaming (Har-Peled & Mazumdar, 2004), dynamic (Henzinger & Kale, 2020) and distributed (Balcan et al., 2013) algorithms for clustering, to imply algorithms for k- E-CENTER in the mentioned settings.
However, note that the claimed composability and reducibility may not hold directly from the definition of coreset (which is more general than covering).
Claim C.1. For generic point set W C CR, ler opt(W) be the optimal i- k--CENTER cost on W. Consider two datasets A, B C Rdd, and suppose SA, SB are (p)) for and (B)) for B, respectively. Then, SAB == SA U Sg an o ( for AU A.B.
Proof. We verify the definition. Consider any point æ AUU U B, then
dist(2; SAB) = dist(r; SA U SB) = min miisdiss(zr, SA), dist(r, Sn)) & minna S <oopt(AU
This finishes the proof.
We also give the following claim on the reducibility of covering.
Claim C.2. Consider a dataset P C Rd, and suppose S is an (a on P. Then any (Bo)t(S)) on an (a + B) opt on P.
Proof. We verify the definition. Consider an arbitrary (3 (S))o(n)) S" on S. For a generic set C Rd and E Rd. let (y) denote the neareset neighbor of y in W. Then for every x E P. we have
dist 5') = dist(x, S'()) I dist(x, 5(x)) + (S()), I appp(()) + Bopt(S) I (a + 3) oP).
This finishes the proof.
D. Recursive Application of Theorem 1.1
In the n regime which we focus on, recursive application of Theorem 1.1 will lead to an improved coreset size, as well as a respective improvement in the runtime for the k-CENTER algorithm. The optimal number of recursion iterations depends on k. In what follows we provide more detailed explanation.
Denote by n; the coreset size after j applications of our algorithm in Theorem 1.1. The first coreset is of size roughly
a = -l++a - n - and this is
M1 km running it again will get us ((a)) of size n2 ~ k (kna B)
13

---

Faster Approximation Algorithms for k-Center via Data Reduction
an improvement when k S
n! Intaa In general, for any fixed j. one apply the algorithm recursively j times and get an 1/ 2/3
O(j az) coreset of asymptotic size ' k Ci ))" .n(n 8)² = 1-a na This is beneficial as long as S n $ However, one should note that our notation hides polylogarithmic factors that will accumulate. Thus one should use the recursion only constant number of times.
1-
Applying (Eppstein et al., 2020) top of the resulting coreset after j iterations will lead to an O(j a)) approximation
I-a" -2
1 to 2/3,7
algorithm for A-CENTER with running time bounded by Ô (n nj 2+ 2) -) Ö(n) +0 k 1-0-2/3 n(a 100
1lu22 δ n. + ki-a 273 na $ +1(++=3)) 3)) for any fixed j.
14


Reviews:
[{"review_id": "5EOAwcljsc", "reviewer": "Reviewer_R2wq", "summary": "The paper \"Faster Approximation Algorithms for k-Center via Data Reduction\" presents a study on efficient algorithms for solving the Euclidean k-Center problem, focusing particularly on large values of k. The main contribution of the paper is the development of approximation algorithms using a data reduction approach. The authors introduce the concept of α-coresets, which are small subsets of the dataset that maintain the approximation characteristics of the full dataset. Specifically, an α-coreset ensures that a β-approximation on the subset provides an (α+β)-approximation on the original dataset.\n\nThe authors propose two coresets with sizes of  k·o(n), significantly reducing the problem size and thus speeding up the existing approximation algorithms. Their approach leads to a near-linear time O(1)-approximation when k = n^c for 0 < c < 1. Through extensive experiments, they demonstrate that these coresets can accelerate the well-known Gonzalez algorithm by 2-4 times, while achieving comparable clustering costs.\nOne key technical contribution is a new efficient construction of consistent hashing, which is used to build these coresets. This method provides competitive parameters while running in polynomial time, which is a substantial improvement over previous exponential-time constructions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful comments. We address the main concerns as follows.\n\n>  General Applicability of Coresets: ... The paper focuses on the Euclidean k-Center problem, so it’s unclear how easily these methods could extend to non-Euclidean metrics or more complex clustering structures.\n\nOur techniques may extend to $\\ell_p$ metrics, for example $\\ell_1$. Indeed, the main Euclidean structure that we utilize is the consistent hashing, and such hashing with competitive bounds for $\\ell_p$ spaces were known to exist, see e.g. [1] (albeit one may need to devise efficient constructions of the hashing, as in our paper).\n\n[1] Arnold Filtser. Scattering and Sparse Partitions, and Their Applications. ACM Transactions on Algorithms, 2024.\n\n> Scalability to Extremely Large Datasets: ... However, it would be valuable to have further evidence on how the approach scales with extremely large datasets (e.g., millions of points and very high-dimensional spaces). Since real-world applications often deal with such data sizes, this would provide more insight into the practicality of the approach.\n\nWe expect that our algorithm would be competitive even in this extreme case.\n\nOn the one hand, the high dimensionality $d$ is a somewhat less important challenge in our case, since one may apply Johnson-Lindenstrauss Transform to make $d = O(\\log n)$, so we do not expect super-high $d$ would have a significant impact to our algorithm. \n\nOn the other hand, for the case of $n$ being millions of points, we already demonstrated the performance of our algorithm in this case, in our kddcup dataset which has $n = 5M$, and $d = 38$.\n\n> Failure Probability: The paper mentions a failure probability for certain parts of the algorithm, but a more detailed discussion on how this failure probability affects the overall performance, particularly in practical settings, would be useful. ... Including error bounds or confidence intervals for the reported performance would help quantify the robustness of the approach. The statistical significance of the experimental results is not addressed. While the authors run multiple trials for their experiments, providing error bars or statistical tests would improve the reliability of the findings, especially when comparing performance across datasets or baselines.\n\nFirst of all, we already take the failure probability into account in our experiments, and we report the cost etc. after we run the algorithms multiple times and take the average.\n\nWe also added new experiments to show the variance of the cost of our algorithm. Please check the following for the results of each dataset:\n\n[Census](https://github.com/r8mtL0pks/ICML25-paper8893-rebuttal/blob/main/Cost%20vs.%20Coreset%20Size%20with%20Variance%20(Census).png)\n\n[Covertype](https://github.com/r8mtL0pks/ICML25-paper8893-rebuttal/blob/main/Cost%20vs.%20Coreset%20Size%20with%20Variance%20(Covertype).png)\n\n[Fashion-MNIST](https://github.com/r8mtL0pks/ICML25-paper8893-rebuttal/blob/main/Cost%20vs.%20Coreset%20Size%20with%20Variance%20(Fashion-MNIST).png)\n\n[KDDCup](https://github.com/r8mtL0pks/ICML25-paper8893-rebuttal/blob/main/Cost%20vs.%20Coreset%20Size%20with%20Variance%20(Kddcup).png)\n\nIn short, the variance is very small compared with the magnitude of the cost.\n\n> how does the algorithm perform on datasets with extreme characteristics, such as sparse or imbalanced data? These scenarios are common in many real-world applications, and understanding how the algorithm handles them could further demonstrate its robustness.\n... The paper doesn’t fully address how well the method handles noisy data or missing values, which are often present in practical datasets. Given that many real-world applications involve imperfect data, providing results for these scenarios would make the paper’s findings even more impactful.\n\nWe actually find imbalanced distribution/outliers in our KDDCup dataset. This also a way to explain why the uniform baseline performs so bad in this dataset (since it misses the extreme point which may affect the $k$-center objective significantly). Nonetheless, our algorithm performs consistently well even in this dataset.\n\nThe missing value seems to be an independent challenge, since it usually requires modeling the missing value to make the problem well-defined. Hence, this is indeed out of the scope of our current algorithm, but it is nonethelss interesting to explore how to model missing values for $k$-center.", "claims_and_evidence": "The claims made in the paper \"Faster Approximation Algorithms for k-Center via Data Reduction\" are generally well-supported by clear and convincing evidence. The authors provide several forms of evidence to back their claims:\n1. Mathematical Proofs: The core idea of constructing α-coresets is supported by rigorous mathematical proofs, particularly in Theorems 1.1 and 1.2, where the existence of efficient coresets and their size bounds are formally established. These theorems are a foundational aspect of the paper's approach, and the authors provide detailed proofs for their correctness.\n2. Experimental Validation:The experimental results provide strong empirical support for the claims. The authors demonstrate that their coreset approach significantly speeds up Gonzalez's algorithm for large values of kk achieving a 2-4x speedup while maintaining comparable clustering costs. \n3. Theoretical Comparisons: The authors also compare their approach with prior work, citing improvements over existing approximation algorithms and the reduction of time complexity. The comparison of their coreset's performance against other methods, such as uniform sampling, further strengthens their claims.\n\nHowever, there are a few claims that could be considered more difficult to evaluate fully without additional clarification or further experimentation:\n1. General Applicability of Coresets: While the paper demonstrates the utility of their coreset approach for large k. the generalizability of the approach to all clustering problems (or problems with significantly different characteristics) could be better explored. The paper focuses on the Euclidean k-Center problem, so it’s unclear how easily these methods could extend to non-Euclidean metrics or more complex clustering structures.\n2. Scalability to Extremely Large Datasets:The experiments show speedups for moderately large datasets. However, it would be valuable to have further evidence on how the approach scales with extremely large datasets (e.g., millions of points and very high-dimensional spaces). Since real-world applications often deal with such data sizes, this would provide more insight into the practicality of the approach.\n3. Failure Probability: The paper mentions a failure probability for certain parts of the algorithm, but a more detailed discussion on how this failure probability affects the overall performance, particularly in practical settings, would be useful.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria in the paper make sense for the problem at hand, and they are well-suited to evaluate the effectiveness of the algorithm.", "theoretical_claims": "I find the theoretical claims in the paper to be reasonable and well-supported by mathematical proofs and established algorithmic techniques. The core ideas (coreset construction, efficient approximation algorithms, and consistent hashing) appear logically sound, and the proofs align with known results in the field of approximation algorithms for clustering.", "experimental_designs_or_analyses": "The experimental design and analyses in the paper are generally sound and valid. However, more experimental results should be added (too few now).\n1. The paper uses four real-world datasets—Kddcup, Covertype, Census, and Fashion-MNIST. These datasets are widely used in machine learning and clustering tasks, making them appropriate benchmarks for evaluating the performance of the proposed method. The datasets are diverse in terms of size and dimensionality, which allows the authors to test their method on both small and large datasets. \n2. The paper evaluates the proposed method using two primary metrics: “Clustering cost” (i.e., the approximation quality) by running the Gonzalez algorithm on the coreset; “Running time” for constructing the coreset and executing the clustering algorithm. These are standard and appropriate evaluation criteria for clustering problems. The clustering cost is essential for assessing the quality of the approximation, and the running time is crucial for understanding the computational efficiency of the approach, especially when the goal is to improve performance for large-scale datasets.", "relation_to_broader_scientific_literature": "The authors advance the state of the art in k-Center clustering by introducing a novel approach that combines data reduction (via α-coresets and consistent hashing) with efficient approximation algorithms. This approach addresses key challenges in scaling k-Center algorithms to large datasets and high-dimensional spaces, making it a significant contribution to the fields of approximation algorithms, clustering, and high-dimensional data analysis. The connection to earlier work on coresets, approximation algorithms, and dimensionality reduction is clear, and the paper builds on these ideas to propose new, more efficient techniques for large-scale clustering.", "essential_references_not_discussed": "The paper provides a thorough review of the relevant literature, and I did not find any essential references that were missing. The key contributions are well-situated within the context of prior work.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper’s novel combination of coreset construction and consistent hashing for improving k-Center algorithms is a major strength. The idea of constructing efficient coresets for large-scale clustering problems is not entirely new, but the specific combination of techniques (such as consistent hashing with competitive parameters and data reduction through α-coresets) brings a new level of efficiency to the problem.The use of geometric hashing for constructing the coreset is another unique aspect of the paper. The new consistent hashing method introduced has competitive parameters and runs in polynomial time, improving upon previous methods that were either slower or had less desirable trade-offs.\n2. The paper is well-structured and clearly written. The key ideas are presented logically, with a clear distinction between the theoretical foundations (coreset construction, consistent hashing) and their practical applications (speedup of the Gonzalez algorithm).The experiments and results are presented in a clear, understandable manner, with sufficient explanation of the trade-offs between coreset size, clustering cost, and running time. The inclusion of real-world datasets adds practical context and strengthens the overall contribution.\n3. The extensive experimental validation provides strong evidence for the effectiveness of the proposed approach. The authors demonstrate a 2-4x speedup in clustering time compared to the Gonzalez algorithm while maintaining similar clustering costs. These empirical results support the theoretical claims and show that the algorithm works well in practice.\n\nWeaknesses:\n1. While the paper demonstrates significant speedups for moderately large datasets, more exploration of edge cases would be beneficial. For example, how does the algorithm perform on datasets with extreme characteristics, such as sparse or imbalanced data? These scenarios are common in many real-world applications, and understanding how the algorithm handles them could further demonstrate its robustness.\n2. The paper doesn’t fully address how well the method handles noisy data or missing values, which are often present in practical datasets. Given that many real-world applications involve imperfect data, providing results for these scenarios would make the paper’s findings even more impactful.\n3. The paper mentions a failure probability for some of the algorithmic steps, but a more detailed discussion of how this impacts overall performance (especially in real-world applications) would be useful. Including error bounds or confidence intervals for the reported performance would help quantify the robustness of the approach. The statistical significance of the experimental results is not addressed. While the authors run multiple trials for their experiments, providing error bars or statistical tests would improve the reliability of the findings, especially when comparing performance across datasets or baselines.", "other_comments_or_suggestions": "I have no additional comments or suggestions.", "questions_for_authors": "In recent yerars, few works concentrate on this area. How can we agree with the need to implement research on this area? Or, in the other words, can you add more ecessity and significance about your work and applications?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n7acDb4TaO", "reviewer": "Reviewer_RhVR", "summary": "The paper proposes speeding up existing algorithms for the $k$- center problem by using coresets. An $\\alpha$-coreset for $k$- center problem is a subset of data such that if you have a $\\beta$ approximation for the $k$- center problem on the subset then you have an $(\\alpha + \\beta) $ approximation for $k$-center on the full data. The authors build coresets using the notion of consistent hashing. They experimentally demonstrate the efficiency of their coresets both in terms of speed up as well as accuracy preservation on real data sets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful comments. We address the main concerns as follows.\n\n> In terms of methods, in coreset literature, people typically obtain centers from the coreset and then report the loss on full data using those centers and compare it with the cost on full data when the problem is directly solved for the full data. Are the same quantities shown in the graphs in Figure 1? It is not clear to me.\n\nWe do compare the cost in the full data. We will clarify this in the next version.\n\n> The authors could have used more sampling techniques as baselines for example they could have used coresets for other clustering problems like $k$-means, $k$-median and used them as baselines also along with uniform sampling.\n\nWe added $k$-median coreset as a baseline, based on the ring sampling method (see e.g. [1][2]) which is widely used in various recent works. We obtain an initial result for the cost evaluation on the Fashion-MNIST dataset, and our result can be found in the following: [Cost evaluation with new baselines -- Fashion-MNIST](https://github.com/r8mtL0pks/ICML25-paper8893-rebuttal/blob/main/All%20Baselines%20(Fashion-MNIST).png). We will complete the experiment on the other datasets in the next version.\n\nIn short, this $k$-median coreset baseline performs similarly to the uniform sampling baseline, and is worse than our algorithm.\n \n[1] Ke Chen. On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications. SIAM Journal on Computing, 2009.\n\n[2] Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn.\nA new coreset framework for clustering. STOC 2021.\n\n\n\n> The paper relies heavily on the idea of consistent hashing which is pretty recent. It would be good to give some more intuitive explanation of this ideas. For e.g. what $\\Gamma$  and $\\Lambda$  mean intuitively.\n\nThe consistent hashing is a space partition, where each part is a bucket. Ideally, we wish each part has a bounded diameter $\\ell$ (which can be picked arbitrarily), and that any subset $S$ that has diameter $O(\\ell)$ is completely contained in one bucket -- this ensures consistency in hashing subsets of $O(\\ell)$ diameter. \n\nCompared with the ideal case, what we actually obtain is relaxed in two aspects: a) the guarantee of consistency is relaxed to intersecting $\\Lambda$ buckets instead of only one, and b) the subset $S$ needs to be small enough, whose diameter must at most $\\ell / \\Gamma$, instead of $O(\\ell)$.\n\nWe will add this explanation in the next version.\n\n> If I understood correctly, in the definition of consistent hashing a smaller $\\Lambda$ is better? Am I correct? If yes, how is the $\\Lambda$  you obtain better than the existing one, since the parameter $c$ is less than 1.\n\nIndeed, our $\\Lambda$ is not better than the state of the art. However, the state of the art that achieves the best $\\Lambda$ has a $2^d$ running time which is too costly. Instead, the focus of this paper is to find an efficient construction that runs in $\\mathrm{poly}(d)$ time, at the cost of a worse yet still useful parameter.\n\n> How does your algorithm perform/ compare with others in case of small and moderate $k$ values?\n\nWe already provided a brief discussion of this in the introduction. Basically, for moderate $k = n^{1 - \\epsilon}$ (where $0 < \\epsilon <1$ is arbitrary), our algorithm can achieve $\\mathrm{poly}(1 / \\epsilon)$-approximation in $\\tilde{O}(nd)$ time. This is better than the other works we mention, which either runs in $O(nk) = O(n^{2 - \\epsilon})$ time, or in $n^{1 + \\mathrm{poly}(\\epsilon)}$ time, but not near-linear in $n$ as we do. \n\n> While I understand hiding the dependence on $\\log n$ in the $\\tilde O$ notation, I am not sure about the dependence on $d$. How will your algorithm perform compared with the Gonzalez and Eppstein algorithm in terms of $d$, especially as we may encounter problems where both $k$ and $d$ are large and using the JL Lemma will have impact on accuracy.\n\nIndeed, we did not attempt to optimize the dependence of $d$ in Theorem 1. The dominating dependence of $d$ comes from Lemma 3.3 (which is a mathematical fact about Minkowski sum), and in other places our algorithm runs (nearly) linear in $d$. Therefore, the dependence of $d$ in the worst-case bound is worse than Gonzalez. \n\nHowever, in practice one may not need to follow the worst-case upper bound of Lemma 3.3. In particular, in our implementation (in the experiments), for any given coreset size, our dependence of $d$ is near-linear.", "claims_and_evidence": "The paper is written clearly and is not very difficult to follow. I find the proofs and the ideas convincing enough.", "methods_and_evaluation_criteria": "The datasets used in the experiments are standard in the literature. In terms of methods, in coreset literature, people typically obtain centers from the coreset and then report the loss on full data using those centers and compare it with the cost on full data when the problem is directly solved for the full data. Are the same quantities shown in the graphs in Figure 1?  It is not clear to me.\n\nThe authors could have used more sampling techniques as baselines for example they could have used coresets for other clustering problems like $k$-means, $k$- median and used them as baselines also along with uniform sampling.", "theoretical_claims": "Most of the proofs are available in the main body of the paper. They are not too difficult to follow for most parts. I checked them to the best of my ability, and they appear correct.", "experimental_designs_or_analyses": "See methods and evaluation criteria.", "relation_to_broader_scientific_literature": "$k$- center is a very well-studied problem and the Gonzalez 2 -approximation algorithm is also well known. The paper combines ideas form literature on high dimensional data science for e.g., the JL -Lemma, covering, hashing etc. to come up with algorithms that speed up the Gonzalez algorithm without harming the accuracy too much. Specifically, the idea is to obtain an almost linear time algorithm for a constant factor approximation for the $k$- center problem for large values of $k$.", "essential_references_not_discussed": "Not to the best of my knowledge", "other_strengths_and_weaknesses": "See responses to other sections", "other_comments_or_suggestions": "1) The paper relies heavily on the idea of consistent hashing which is pretty recent. It would be good to give some more intuitive explanation of this ideas. For e.g. what $\\Gamma $ and $\\Lambda$ mean intuitively.", "questions_for_authors": "1) If I understood correctly, in the definition of consistent hashing a smaller $\\Lambda$ is better? Am I correct? If yes, how is the $\\Lambda$ you obtain better than the existing one, since the parameter $c$ is less than 1. \n\n2) How does your algorithm perform/ compare with others in case of small and moderate $k$- values?\n\n3) While I understand hiding the dependence on $\\log n$ in the $\\tilde {O}$ notation, I am not sure about the dependence on $d$. How will your algorithm perform compared with the Gonzalez and Eppstein algorithm in terms of $d$, especially as we may encounter problems where both $k$ and $d$ are large and using the JL Lemma will have impact on accuracy.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "sAW6Scjhjv", "reviewer": "Reviewer_WZSx", "summary": "This paper studies fast algorithms for the k-Center problem, focusing on the regime of large k. It presents a novel approach based on the corsets that achieves better running time.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful comments. We address the main concerns as follows.\n\n> The algorithm achieves a constant factor approximation but not 2.\n\nWe agree that achieving a factor of $2$ in near-linear time when $k = n^{1 - \\epsilon}$ is an ideal goal and is certainly an interesting open question. Although our work does not directly resolve it, we still offer relevant techniques for attacking the problem, which has potential to lead to small factor approximation (e.g., a ratio of $4$).", "claims_and_evidence": "The claims are supported by the evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, the paper is sound.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This work is important and impactful in the field of k-center.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n- The problem considered is important, and the improvements in running time are significant.\n- The result is clearly stated, and the paper is well-written.\n- The regime of k considered is interesting.\n- The novelty of the work is on par with the expectations of this conference.\n\nWeaknesses:\n- The algorithm achieves a constant factor approximation but not 2.\n- In some cases, the performance is close to or even worse than the baselines.", "other_comments_or_suggestions": "No", "questions_for_authors": "I think the paper is in a good shape and I do not have any questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YuLXGiZQfD", "reviewer": "Reviewer_MqS4", "summary": "This paper presents fast algorithms for approximate $k$-center in Euclidean spaces. In general metric spaces, it is not possible to be faster than $n\\cdot k$ for any bounded approximation. A folklore result in Euclidean spaces yields a $O(n\\cdot(k + d)\\cdot\\varepsilon^{-2}\\log n)$ for a $2+\\varepsilon$ approximation. Following a standard JL mapping to low dimensions, the authors give a running time of $O(n + k^{1+1/\\alpha^2}n^{\\alpha^{-2/3}})$ (which I and I imagine also the authors consider the main result) and an alternative algorithm running in time $O(nk^{1/\\alpha^2})$.\n\nThe main result is based on an efficient implementation of consistent hashing: a bucketing technique that allows for fast approximate covering of the data set.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful comments. We address the main concerns as follows.\n\n> As a alternative for deriving the  bound, one could also first construct a spanner for high dimensional Euclidean spaces by Sariel Har-Peled, Piotr Indyk, Sidiropoulos (SODA'13) and then run an algorithm for k-center in sparse graphs by Thorup (SICOMP'04). Since these results were published earlier than the Eppstein, Har-Peled, Sidiropoulos paper, they should at least be mentioned.\n\nThanks for suggesting these references. We will add these in the next version.\n\n> The experiments could be better. The authors mainly compare between coreset-based approaches, but this leaves out other option. While the uniform sampling can serve as a sanity check for \"is the data set trivial to cluster\" and should be included, I am not sure what the point of the low-dimensional coreset construction is, which is designed for small approximation factors.\n\nAlthough conceptually the low dimension baseline is not very relevant to our regime, we find the construction algorithm is in fact very similar to our high dimensional coreset. In particular, in an optimized variant/implementation of the low dimensional baseline, it is the same with our high-dimensional algorithm except that the random shift is skipped (and is replaced with a fixed grid). It is thus interesting to compare with such a baseline to demonstrate the usefulness of the random shift.\n\n> A more interesting comparison would have been for using a tree embedding ... which has $\\mathrm{polylog}(n)$ approximation ...\n\nFirst, we note that while tree embedding has $O(\\log n)$ distortion, it has bounded distortion only in the expected sense, and this is too weak for $k$-center where we care about the **max** distance. Therefore, we think that tree embedding cannot yield a finite ratio for $k$-center, at least not $\\mathrm{polylog}(n)$.\n\nNonetheless, we still try to add tree embedding as a new baseline, and we rerun the experiment on the Fashion-MNIST baseline. The initial result is listed here: [Cost evaluation with new baselines -- Fashion-MNIST](https://github.com/r8mtL0pks/ICML25-paper8893-rebuttal/blob/main/All%20Baselines%20(Fashion-MNIST).png). Indeed, it shows that tree embedding performs poorly on this dataset.\n\n> One other question that immediately came to my mind is why the main result cannot be applied recursively. While the approximation will deteriorate, the dependency on $n$ could be reduced even more. I see no clear reason why that should not work and it would be nice if the authors either included it (with a discussion on how the parameters would change) or explained why it wouldn't work.\n\nWe thank the reviewer for the interesting suggestion. The short answer is that in some parameter regimes (and in particular in the  $k = n^{1 - \\epsilon}$ regime which we focus on), a recursive application will lead to an improved coreset size, and a respective improvement in the runtime for the $k$-center algorithm. The optimal number of recursion iterations depends on $k$. In what follows we provide a more detailed explanation.\n\nDenote by $n_j$ the coreset size after $j$ applications of our algorithm.\nThe first coreset is of size roughly $n_1\\sim k n^{\\alpha^{-2/3}}$, running it again will get us an $O(\\alpha)$-coreset of size $n_{2}\\sim k\\cdot\\left(kn^{\\alpha^{-\\frac{2}{3}}}\\right)^{\\alpha^{-\\frac{2}{3}}}=k^{1+\\alpha^{-\\frac{2}{3}}}\\cdot n^{\\alpha^{-\\frac{4}{3}}}$, and this is an improvement when $k\\le n^{1-\\alpha^{-\\frac{2}{3}}}$.\nIn general, for any fixed $j$, one can apply the algorithm recursively $j$ times and get an $O(j\\cdot\\alpha)$ coreset of asymptotic  size $n_{j}\\sim k^{\\sum_{q=0}^{j-1}\\left(\\alpha^{-\\frac{2}{3}}\\right)^{q}}\\cdot n^{\\left(\\alpha^{-\\frac{2}{3}}\\right)^{j}}=k^{\\frac{1-(\\alpha^{-2/3})^{j}}{1-\\alpha^{-2/3}}}n^{(\\alpha^{-2/3})^{j}}$. This is beneficial as long as  $k\\le n_j^{1-\\alpha^{-\\frac{2}{3}}}$. However, one should note that our notation hides polylogarithmic factors that will accumulate. Thus one should use the recursion only a constant number of times. \n\nApplying [EHS20] on top of the resulting coreset after $j$ iterations will lead to an $O(j\\cdot\\alpha)$ approximation algorithm for $k$-center with running time bounded by $\\tilde{O}\\left(n+n_{j}^{1+\\alpha^{-2}}\\right)=\\tilde{O}(n)+\\tilde{O}\\left(k^{\\frac{1-(\\alpha^{-2/3})^{j}}{1-\\alpha^{-2/3}}}n^{(\\alpha^{-2/3})^{j}}\\right)^{1+\\alpha^{-2}}\\le\\tilde{O}\\left(n+k^{\\frac{1+\\alpha^{-2}}{1-\\alpha^{-2/3}}}n^{\\alpha^{-\\frac{2j}{3}}\\cdot(1+\\alpha^{-2})}\\right)$, for any fixed $j$.\n\nWe will do a more detailed calculation and add it to the next version.", "claims_and_evidence": "The results are nice and as far as I can tell correct. I would be a bit more excited if the the authors had managed to get a clean $\\tilde{O}(n+k^{1+1/\\alpha^2})$ or even a $O(n+\\text{poly}(k))$ bound, as long as the approximation factor is non-trivial. Applying their ideas recursively would maybe be a step in that direction (see further below).\n\nThe experiments could be a bit better (see further below).\n\nI ultimately decided on an accept. The result is strong, even it could be improved and well within the scope of ICML.", "methods_and_evaluation_criteria": "-", "theoretical_claims": "-", "experimental_designs_or_analyses": "-", "relation_to_broader_scientific_literature": "Trading accuracy for running time has been an important topic, especially recently. In particular linear time or nearly linear time algorithms tend to be the most useful results for implementation. This paper gives adds to this research.\n\nWhile I wouldn't consider k-center the most interesting objective in this line of research and it is not clear whether ideas for k-center extend to other problems, it is neverthess important.", "essential_references_not_discussed": "As a alternative for deriving the $O(n^{1+1/\\alpha^2})$ bound, one could also first construct a spanner for high dimensional Euclidean spaces by Sariel Har-Peled, Piotr Indyk, Sidiropoulos (SODA'13) and then run an algorithm for k-center in sparse graphs by Thorup (SICOMP'04). Since these results were published earlier than the Eppstein, Har-Peled, Sidiropoulos paper, they should at least be mentioned.", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "-", "questions_for_authors": "The experiments could be better. The authors mainly compare between coreset-based approaches, but this leaves out other option. While the uniform sampling can serve as a sanity check for \"is the data set trivial to cluster\" and should be included, I am not sure what the point of the low-dimensional coreset construction is, which is designed for small approximation factors. \n\nA more interesting comparison would have been for using a tree embedding, which has $poly(\\log n)$ distortion, followed by a linear time algorithm for k-center in trees. These algorithms are almost certain to be equally fast or perhaps even faster than what the authors are presenting, especially given the large values of $k$ which is the regime of interest here. If a tree-embedding based approach is similarly accurate, it would be good to know. I would recommend the paper even if the tree-embedding results were empirically better, as they will yield provably worse theoretical bounds.\n\nOne other question that immediately came to my mind is why the main result cannot be applied recursively. While the approximation will deteriorate, the dependency on $n$ could be reduced even more. I see no clear reason why that should not work and it would be nice if the authors either included it (with a discussion on how the parameters would change) or explained why it wouldn't work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a new algorithm for Euclidean k-center with constant approximation and faster runtime in the large k regime. In this problem, we are given n points in the Euclidean space and the goal is to select k centers in the ambient space so that the maximum distance between any point in the dataset and the nearest center is minimized. The result is achieved via new consistent hashing constructions. All reviewers appreciate the importance of the problem and the theoretical improvement. The theoretical approximation factor is a large constant factor but in experiments, the new algorithm seems competitive with the classical method while improving the runtime by up to a factor 4. The reviewers had some concerns regarding the experiments but this aspect has been improved in the rebuttals.
Decision: Accept (poster)