Pith. sign in

REVIEW 1 major objections 4 minor 41 references

Faster Approximation Algorithms for k-Center via Data Reduction

T0 review · 1 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that Euclidean k-center admits an O(α)-coreset of size O~(k n^{1/α^{2/3}}) computed in near-linear time, yielding an O(1)-approximation for k=n^c.

desk verdict Solid, accept-worthy theory paper with a real advance for large-k Euclidean k-center; the main caveat is a load-bearing external volume bound that is cited but not proved. read the letter →

arxiv 2502.05888 v1 pith:ODM3PABC submitted 2025-02-09 cs.DS

Arnold Filtser , Shaofeng H.-C. Jiang , Yi Li , Anurag Murty Naredla , Ioannis Psarros , Qiaoyuan Yang , Qin Zhang This is my paper · ORCID
classification cs.DS MSC 68W2568U0568Q25
keywords k-centercoresetconsistenthashingrandomlyshiftedgridEuclideanclusteringapproximationalgorithmslarge-kregimenear-lineartime
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that the Euclidean k-center problem can be solved to a constant approximation in near-linear time even when the number of centers k is as large as n^c for any 0

What carries the argument

The central object is the (Γ,Λ,ℓ)-consistent hashing of Definition 3.1: a distribution over maps φ: R^d → R^d such that each cell $φ^{{-1}}$(x) has diameter at most ℓ and the expected number of cells intersecting any ball of radius ℓ/Γ is at most Λ. The paper constructs one by a uniformly randomly shifted integer grid, φ(x) = ⌊x+v⌋, and proves the bound Λ = poly(d)·exp(O(d/$β^{{2/3}}$)) from a volume bound on a unit cube inflated by a ball. This hash turns each optimal cluster—a ball of radius opt—into at most Λ cells, so one representative per nonempty cell is a covering of size kΛ; after projection to O(log n) dimensions, the size becomes k $n^{{O(1/α^{2/3}}$)}. The companion machinery is the covering-to-coreset reduction, which says a (β·opt)-covering is a β-coreset.

What would settle it

Directly evaluate the volume of [0,1]^d ⊕ B(0,r) for r=$\sqrt$(d)/β at, say, d=500 and β=2 by Monte Carlo integration; if the log-volume grows faster than Θ(d/$β^{{2/3}}$)—or equivalently, if a randomly shifted unit grid is hit by many more than exp(O(d/$β^{{2/3}}$)) cells—then Lemma 3.2's parameter bound fails and the coreset size theorem does not follow.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that approximation-preserving data reduction for k-center can be done by finding a small covering: a subset S of P such that every point is within O(α·opt) of S, because any β-approximation on such an S is an (α+β)-approximation on P. The main construction is a new consistent hashing based on a randomly shifted grid: with parameter β, every ball of radius $\sqrt$(d)/β intersects only poly(d)·exp(O(d/$β^{{2/3}}$)) grid cells in expectation, evaluable in O(d) time—the first polynomial-time consistent hashing with this trade-off. Composed with a random projection to O(log n) dimensions, this yields the near-linear coreset of Theorem 1.1; a separate sampling argument with approximate nearest neighbors yields the k·polylog(n)-size coreset of Theorem 1.2 in O~(n $k^{{1/α^2}}$) time.

Load-bearing premise

The proof leans on an imported volume bound—that inflating the unit cube by a ball of radius r increases its volume only by a factor exp(O($d^{{2/3}}$$r^{{2/3}}$))—and if that bound's exponent is actually larger, the coreset size grows faster with the approximation parameter and the near-linear regime would require a worse trade-off.

Editorial extensions

If this is right

  • Running the known O(n^{1+1/α^2})-time O(α)-approximation algorithm on the Theorem 1.1 coreset gives an O(α)-approximation in O~(n + k^{1+1/α^2} n^{O(1/α^{2/3})}) time, improving the previous running time.
  • For k = n^c with 0<c<1, the coreset yields a near-linear-time O(1)-approximation algorithm for Euclidean k-center.
  • The Theorem 1.2 coreset gives an O(α)-approximation in O~(n k^{1/α^2}) time with coreset size k·polylog(n).
  • Because the coresets are coverings, they compose and reduce, so they fit into merge-and-reduce schemes for streaming, dynamic, and distributed clustering.
  • Experiments show the coreset-accelerated greedy 2-approximation is up to 4 times faster with cost within about 1.3 times on four real datasets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The new consistent hashing is likely useful beyond k-center: any high-dimensional geometric algorithm that relies on sparse partitions can now use a randomly shifted grid with polynomial-time evaluation instead of an exponential-time construction.
  • The near-linear guarantee depends on reducing dimension with a random projection; without that step the coreset size carries an exp(d/β^{2/3}) factor, so the approach does not remove the exponential dependence on dimension in the coreset size.
  • A natural testable conjecture is that the exponent 2/3 in the coreset exponent is tight for this construction, since it comes directly from the inflated-cube volume bound rather than from an information-theoretic argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. This paper studies Euclidean k-center in the large-k regime through α-coresets. It gives two coreset constructions: Theorem 1.1 builds an O(α)-coreset of size O~(k n^{1/α^{2/3}}) in O~(n) time using a new consistent-hashing construction based on a randomly shifted grid, and Theorem 1.2 builds an O(α)-coreset of size k polylog n in O~(n k^{1/α^2}) time using random sampling and approximate nearest neighbor search. Composed with the EHS20 approximation algorithm, these yield improved time-approximation trade-offs, including a near-linear-time O(1)-approximation whenever k = n^c for 0 < c < 1. The paper also contains an experimental evaluation of the Theorem 1.1 coreset on four real datasets.

Significance. The results are a meaningful step for k-center in the large-k regime: they remove the superlinear k-factor from Gonzalez's algorithm for k = n^c, and the consistent-hashing construction with polynomial-time evaluation is a clean and potentially reusable tool. The proofs are largely self-contained, with explicit constants in the covering lemmas and no fitted parameters or circular dependencies; the claimed trade-offs follow from concrete reduction arguments. I regard the central claims as sound and the main theorem as a significant advance, provided the small proof gaps identified below are repaired.

major comments (1)
  1. [Section 5, Lemma 5.2] The tail argument counts ⌈log n⌉ successful halvings and then asserts that Q(j') is empty, but after ⌈log_2 n⌉ halvings a set can still have size 1, which is not empty; the argument needs ⌈log_2 n⌉+1 successful halvings. The same value L = 5⌈log n⌉ and the binomial tail bound with m+1 still give failure probability below 1/n, so this is a local repair, but it is necessary because Lemma 5.2 is the key correctness lemma for Theorem 1.2.
minor comments (4)
  1. [Section 3, Lemma 3.3] The exponent 2/3 that drives the coreset size in Theorem 1.1 is imported from the volume bound of [AKS14] without proof; since the near-linear claim for k = n^c depends on this exact r^{2/3} scaling, I suggest including a proof or a short self-contained derivation in an appendix to make the dependency transparent. I consider this a verification gap rather than a detected error.
  2. [Theorem 1.1 proof] The proof writes f : R^d → R^{d'} after invoking the JL lemma, but Lemma 4.3 only provides f : P → R^{d'}; the subsequent argument is valid using f on P alone, and injectivity on P follows from (1−ε) > 0, so the notation should be adjusted.
  3. [Lemma 3.2 / Theorem 1.1] Lemma 3.2 is stated for β ≥ √(2π), while Theorem 1.1 is stated for every α ≥ 1; the proof should explicitly set β = max(α, Θ(1)) so that the O(α) notation absorbs the constant regime.
  4. [Definition 3.1] The diameter condition should quantify over points in the image of φ; for y outside the range, φ^{-1}(y) is empty, so the current wording is slightly imprecise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all load-bearing steps are self-contained proofs or independent external lemmas.

full rationale

The derivation chain is linear: Lemma 4.1 reduces coresets to coverings; Lemma 4.2 constructs a covering from a consistent hashing; Lemma 3.2 proves the hashing parameters from a randomized grid and the volume bound of Lemma 3.3; Theorem 1.1 then applies JL to reduce dimension. No step assumes the target approximation theorem or fits a parameter to the quantity it later 'predicts.' The coreset size is computed, not calibrated, from t_beta, and t_beta follows from an external published volume bound ([AKS14], Lemma 3.1), not from any self-citation. Self-citations to [CJK+22], [CFJ+23], and [Fil24] appear only as background or comparisons, and [JKS24] is a footnote; none carries the proof of the main theorem. The only noteworthy gap is that Lemma 3.3 is quoted without proof, but this is a verification/correctness concern, not circularity, since the cited result is independent of the present paper and does not encode the k-center theorem.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard external tools rather than new assumptions: the Johnson-Lindenstrauss lemma for dimension reduction, the [AKS14] volume bound used to analyze the shifted grid, the [EHS20] algorithm whose runtime is improved by the coreset, and the [AI06] ANN structure used by the sampling coreset. No constants are fitted to data; alpha, beta, and k are inputs. The only new object is the efficient consistent hashing distribution, which is proven, not postulated.

assumptions (5)
  • standard math Johnson-Lindenstrauss lemma: an n-point Euclidean set can be embedded into O(epsilon^(-2) log n) dimensions with all pairwise distances within factor (1+/-epsilon).
    Invoked as Lemma 4.3 in the proof of Theorem 1.1 to reduce dimension before applying grid hashing.
  • standard math Volume bound of [AKS14] Lemma 3.3: vol([0,1]^d + B(0,r)) <= poly(d) exp((3/2)(2 pi)^(1/3) d^(2/3) r^(2/3)) for 0 < r <= sqrt(d/(2 pi)).
    Used in Lemma 3.2 to bound the expected number of grid cells intersecting a ball of radius sqrt(d)/beta, determining the exponent 2/3 in the consistent hashing parameter.
  • standard math The [EHS20] algorithm computes an O(alpha)-approximation to Euclidean k-center in O(n^(1+1/alpha^2)) time.
    Theorems 1.1 and 1.2 obtain their final running times by running this exact algorithm on the coreset, as shown in Table 1.
  • standard math The [AI06] data structure supports O(beta)-approximate nearest neighbor queries with preprocessing O(m^(1+1/beta^2)) and query O(m^(1/beta^2)).
    Used in Algorithm 2 to determine which points lie within 2 beta tau of the sampled points in the sampling-based covering for Theorem 1.2.
  • standard math Gonzalez's algorithm yields a 2-approximation to k-center whose centers lie in the input set.
    Used in the proof of Theorem 1.1 to show opt(P') <= 2(1+epsilon) opt(P) after the JL transform.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Approximation Algorithms for k-Center via Data Reduction." pith.science (2026). https://pith.science/paper/ODM3PABC

@misc{pith2026250205888,
  author       = {Pith},
  title        = {Pith review of: Faster Approximation Algorithms for k-Center via Data Reduction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ODM3PABC}},
  note         = {Machine review of arXiv:2502.05888}
}
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.

Figures

Figures reproduced from arXiv: 2502.05888 by the authors.

Figure 1
Figure 1. The trade-off between the coreset size and the [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. The trade-off between the coreset size and the running time for all baselines in each [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 26 canonical work pages

  1. [1]

    Emiris, Loukas Kavouras, and Ioannis Psarros

    Zeta Avarikioti, Ioannis Z. Emiris, Loukas Kavouras, and Ioannis Psarros. High-dimensional approximate r-nets. Algorithmica , 82(6):1675--1702, 2020

    work page 2020

  2. [2]

    Agarwal, Sariel Har - Peled, and Kasturi R

    Pankaj K. Agarwal, Sariel Har - Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. ACM , 51(4):606--635, 2004

    2004

  3. [3]

    Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions

    Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In FOCS , pages 459--468. IEEE Computer Society, 2006

    work page 2006

  4. [4]

    Reporting neighbors in high-dimensional euclidean space

    Dror Aiger, Haim Kaplan, and Micha Sharir. Reporting neighbors in high-dimensional euclidean space. SIAM Journal on Computing , 43(4):1363--1395, 2014

    work page 2014

  5. [5]

    Ellis Hershkowitz, and Rajmohan Rajaraman

    Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D. Ellis Hershkowitz, and Rajmohan Rajaraman. One tree to rule them all: Poly-logarithmic universal steiner tree. In FOCS , pages 60--76. IEEE , 2023

    work page 2023

  6. [6]

    Split and join: Strong partitions and universal steiner trees for graphs

    Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, and Srinivasagopalan Srivathsan. Split and join: Strong partitions and universal steiner trees for graphs. In FOCS , pages 81--90. IEEE Computer Society, 2012

    work page 2012

  7. [7]

    Mirrokni

    MohammadHossein Bateni, Hossein Esfandiari, Manuela Fischer, and Vahab S. Mirrokni. Extreme k-center clustering. In AAAI , pages 3941--3949. AAAI Press, 2021

    work page 2021

  8. [8]

    Distributed k-means and k-median clustering on general communication topologies

    Maria - Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general communication topologies. In NIPS , pages 1995--2003, 2013

    1995

Show all 41 references
  1. [9]

    Vladimir Braverman, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering with missing values. In NeurIPS , pages 17360--17372, 2021

    2021

  2. [10]

    Covertype

    Jock Blackard. Covertype . UCI Machine Learning Repository, 1998. DOI : https://doi.org/10.24432/C50K5N

    1998 doi

  3. [11]

    On parallel k-center clustering

    Sam Coy, Artur Czumaj, and Gopinath Mishra. On parallel k-center clustering. In SPAA , pages 65--75. ACM , 2023

    2023

  4. [12]

    Artur Czumaj, Arnold Filtser, Shaofeng H. - C. Jiang, Robert Krauthgamer, Pavel Vesel \' y , and Mingwei Yang. Streaming facility location in high dimension via new geometric hashing. CoRR , abs/2204.02095, 2023. see also conference version in FOCS22. URL: https://doi.org/10.4...

    2023 doi arXiv

  5. [13]

    Artur Czumaj, Guichen Gao, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Pavel Vesel \' y . Fully-scalable MPC algorithms for clustering in high dimension. In ICALP , volume 297 of LIPIcs , pages 50:1--50:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    2024

  6. [14]

    Amir Carmel, Chengzhi Guo, Shaofeng H. - C. Jiang, and Robert Krauthgamer. Coresets for 1-center in _1 metrics. In ITCS , 2025

    2025

  7. [15]

    Artur Czumaj, Shaofeng H. - C. Jiang, Robert Krauthgamer, Pavel Vesel \' y , and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. In FOCS , pages 450--461. IEEE , 2022

    2022

  8. [16]

    Streaming algorithms for robust distinct elements

    Di Chen and Qin Zhang. Streaming algorithms for robust distinct elements. In SIGMOD Conference , pages 1433--1447. ACM , 2016

    2016

  9. [17]

    Data fusion: resolving data conflicts for integration

    Xin Luna Dong and Felix Naumann. Data fusion: resolving data conflicts for integration. Proceedings of the VLDB Endowment , 2(2):1654--1655, 2009

    2009

  10. [18]

    Approximate greedy clustering and distance selection for graph metrics

    David Eppstein, Sariel Har - Peled, and Anastasios Sidiropoulos. Approximate greedy clustering and distance selection for graph metrics. J. Comput. Geom. , 11(1):629--652, 2020

    2020

  11. [19]

    Fast clustering using mapreduce

    Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using mapreduce. In KDD , pages 681--689. ACM , 2011

    2011

  12. [20]

    Tom \' a s Feder and Daniel H. Greene. Optimal algorithms for approximate clustering. In STOC , pages 434--444. ACM , 1988

    1988

  13. [21]

    Scattering and sparse partitions, and their applications

    Arnold Filtser. Scattering and sparse partitions, and their applications. ACM Trans. Algorithms , 20(4):30:1--30:42, 2024. See also conference version in ICALP20

    2024

  14. [22]

    A PTAS for k-means clustering based on weak coresets

    Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A PTAS for k-means clustering based on weak coresets. In SoCG , pages 11--18. ACM , 2007

    2007

  15. [23]

    Gonzalez

    Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. , 38:293--306, 1985

    1985

  16. [24]

    Lingxiao Huang, Shaofeng H. - C. Jiang, and Jianing Lou. The power of uniform sampling for k-median. In ICML , volume 202 of Proceedings of Machine Learning Research , pages 13933--13956. PMLR , 2023

    2023

  17. [25]

    Fully-dynamic coresets

    Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In ESA , volume 173 of LIPIcs , pages 57:1--57:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    2020

  18. [26]

    On coresets for k-means and k-median clustering

    Sariel Har - Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In STOC , pages 291--300. ACM , 2004

    2004

  19. [27]

    Hochbaum and David B

    Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res. , 10(2):180--184, 1985

    1985

  20. [28]

    Hochbaum and David B

    Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. ACM , 33(3):533--550, 1986

    1986

  21. [29]

    Data quality and record linkage techniques , volume 1

    Thomas N Herzog, Fritz J Scheuren, and William E Winkler. Data quality and record linkage techniques , volume 1. Springer, 2007

    2007

  22. [30]

    Product quantization for nearest neighbor search

    Herv \' e J \' e gou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. , 33(1):117--128, 2011

    2011

  23. [31]

    Shaofeng H. - C. Jiang, Robert Krauthgamer, and Shay Sapir. Moderate dimension reduction for k-center clustering. In SoCG , volume 293 of LIPIcs , pages 64:1--64:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    2024

  24. [32]

    Extensions of Lipschitz maps into a Hilbert space

    William Johnson and Joram Lindenstrauss. Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics , 26:189--206, 01 1984. https://doi.org/10.1090/conm/026/737400 doi:10.1090/conm/026/737400

    1984 doi

  25. [33]

    Universal approximations for tsp, steiner tree, and set cover

    Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for tsp, steiner tree, and set cover. In STOC , pages 386--395. ACM , 2005

    2005

  26. [34]

    Record linkage: similarity measures and algorithms

    Nick Koudas, Sunita Sarawagi, and Divesh Srivastava. Record linkage: similarity measures and algorithms. In SIGMOD , pages 802--803. ACM, 2006

    2006

  27. [35]

    Almost-linear time approximation algorithm to euclidean k-median and k-means

    Max Dupr \' e la Tour and David Saulpic. Almost-linear time approximation algorithm to euclidean k-median and k-means. CoRR , abs/2407.11217, 2024

    2024 arXiv

  28. [36]

    Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms

    Alexander Munteanu and Chris Schwiegelshohn. Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms. K \" u nstliche Intell. , 32(1):37--53, 2018

    2018

  29. [37]

    New results on the complexity of p-center problems

    Nimrod Megiddo and Arie Tamir. New results on the complexity of p-center problems. SIAM J. Comput. , 12(4):751--758, 1983

    1983

  30. [38]

    US Census Data (1990)

    Chris Meek, Bo Thiesson, and David Heckerman. US Census Data (1990) . UCI Machine Learning Repository, 2001. DOI : https://doi.org/10.24432/C5VP42

    1990 doi

  31. [39]

    KDD Cup 1999 Data

    Salvatore Stolfo, Wei Fan, Wenke Lee, Andreas Prodromidis, and Philip Chan. KDD Cup 1999 Data . UCI Machine Learning Repository, 1999. DOI : https://doi.org/10.24432/C51C7N

    1999 doi

  32. [40]

    High-Dimensional Probability: An Introduction with Applications in Data Science

    Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science . Cambridge University Press, 2018

    2018

  33. [41]

    Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017

    Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017. https://arxiv.org/abs/cs.LG/1708.07747 arXiv:cs.LG/1708.07747

    2017 arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.