Pith. sign in

REVIEW 2 major objections 6 minor 61 references

Faster Randomized and Deterministic k-Clustering on Graphs

T0 review · 2 major / 6 minor · reviewed 2026-07-09 · glm-5.2

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

Pith's one-line read Deterministic nearly-linear k-center on graphs resolves open problem

desk verdict Solid paper resolving an open problem; k-center result is clean, (k,z)-clustering results are real improvements but lean heavily on external results read the letter →

arxiv 2607.07615 v1 pith:RK2ZB6FS submitted 2026-07-08 cs.DS

Sebastian Forster , Yasamin Nazari , Rajath Rao K. N. , Antonis Skarlatos This is my paper · ORCID
classification cs.DS MSC 68W2568W2005C85
keywords k-centerk-clusteringgraphalgorithmsapproximationnearly-lineartimedeterministicdynamicshortestpathsdistanceoracles
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 proves that four fundamental graph clustering problems—k-center, k-center with outliers, randomized (k,z)-clustering, and deterministic (k,z)-clustering—can be solved in nearly-linear time in the number of graph edges. The central mechanism is the observation that the Gonzalez greedy algorithm's iterative farthest-point selection can be implemented by maintaining approximate shortest-path distances from a super-source vertex connected to all selected centers, using a dynamic single-source shortest-path data structure that supports only source-edge insertions. Each time a new center is chosen, a zero-weight edge from the super-source to that center is inserted, and the data structure efficiently updates all distance estimates in total time near-linear in m, rather than recomputing distances from scratch at each of the k iterations. For the deterministic (k,z)-clustering result, the authors additionally repurpose the bunch-and-cluster machinery of the Thorup-Zwick distance oracle to deterministically estimate ball sizes, replacing a randomized sampling procedure.

What carries the argument

Source-Insertion SSSP data structure maintaining approximate distances under source-edge insertions; super-source vertex connected to selected centers; truncated Dijkstra for ball computations; Thorup-Zwick bunches and clusters for deterministic ball-size estimation

What would settle it

A counterexample graph and sequence of source-edge insertions for which the Source-Insertion SSSP data structure either violates the (1+ε)-approximation guarantee or exceeds the Õ(m) total update time bound, particularly for the specific pattern of k zero-weight source-edge insertions interleaved with distance queries used by the clustering algorithms.

Watch

Extended reading notes

Core claim

The key technical insight is that the Gonzalez greedy framework for k-center, and the Mettu-Plaxton greedy framework for (k,z)-clustering, both have an outer loop that iteratively adds a center to the current set—a pattern that matches the update model of a Source-Insertion SSSP data structure, which maintains (1+ε)-approximate distances from a source vertex when zero-weight edges are inserted from the source to selected vertices. By running this data structure on an augmented graph with a super-source connected to all chosen centers, the farthest vertex (for k-center) or the forbidding loop (for (k,z)-clustering) can be implemented in total time Õ(m/ε) across all k iterations, rather than Õ

Load-bearing premise

The correctness and running-time guarantees of all four main results depend on the Source-Insertion SSSP data structure of Górkiewicz and Karczmarz, cited as an external result. If this data structure does not correctly maintain (1+ε)-approximate distances under source-edge insertions in Õ(m) total update time, or if its vertex-touch reporting mechanism does not perform as stated, the running time and approximation guarantees of every algorithm in this paper would be affected

Editorial extensions

If this is right

  • The Source-Insertion SSSP pattern—using a dynamic shortest-path structure to amortize the cost of iteratively adding centers—may apply to other greedy or incremental algorithms on graphs that require repeated distance computations from a growing set of source vertices.
  • The Thorup-Zwick distance oracle, traditionally used for pairwise distance queries, is shown to be useful for deterministic ball-size estimation, suggesting further applications in derandomizing graph algorithms that rely on ball-size sampling.
  • The deterministic k-center result matches the known lower bound of 2 for incremental algorithms, meaning the approximation factor is optimal up to the additive ε, closing the gap for deterministic graph k-center.
  • The near-linear time for randomized (k,z)-clustering subsumes prior results for k-median and extends to k-means and general z, suggesting that the graph setting admits faster algorithms than the general metric setting, where a kn distance-query lower bound applies.
  • The technique of computing approximate balls via truncated Dijkstra, where each edge is relaxed at most twice per radius scale, may be applicable to other graph algorithms that need to compute neighborhoods around dynamically selected centers.

Reading between the lines

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

  • If the Source-Insertion SSSP data structure can be extended to handle edge deletions or general edge updates (not just source-edge insertions), the techniques here might yield dynamic or decremental clustering algorithms with similar running times.
  • The deterministic ball-size estimation via Thorup-Zwick clusters introduces a polynomial approximation factor depending on the oracle parameter t; whether this factor can be reduced to a true constant independent of t, perhaps via a different deterministic ball-estimation method, remains open.
  • The connection between dynamic shortest-path algorithms and greedy clustering suggests that future improvements to partially dynamic SSSP data structures would directly improve the running times of these clustering algorithms.
  • For graphs with special structure (e.g., planar, bounded-genus, or minor-free), the Thorup-Zwick preprocessing cost might be reducible, potentially yielding deterministic near-linear time (k,z)-clustering with constant approximation on such graph classes.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. This paper presents four main results on k-clustering in weighted undirected graphs: (1) a deterministic (2+ε)-approximation for incremental k-center in Õ(m/ε) time, resolving an open problem of Abboud et al. [SOSA 2023]; (2) a randomized (2+ε)-approximation for k-center with outliers in Õ(m/ε) time; (3) a randomized O(1)-approximation for incremental (k,z)-clustering in Õ(m log Δ) time; and (4) a deterministic O(poly(t))-approximation for incremental (k,z)-clustering in Õ(t·m·n^{1/t} + m/ε) time. The techniques combine the Source-Insertion SSSP data structure of Górkiewicz and Karczmarz [ICALP 2025], the greedy framework of Dupré la Tour and Saulpic [ICALP 2026], Cohen's ball-size estimation, and the Thorup-Zwick distance oracle hierarchy. The k-center result (Theorem 1.1) is clean and self-contained. The (k,z)-clustering results build on external tools in a modular way.

Significance. The deterministic k-center result (Theorem 1.1) resolves a stated open problem and is a clean contribution. The identification of the Source-Insertion SSSP paradigm as a useful primitive for graph clustering is a valuable technical insight. The randomized (k,z)-clustering result (Theorem 1.3) improves prior running times to nearly-linear. The deterministic (k,z)-clustering result (Theorem 1.4) gives the first deterministic close-to-linear-time algorithm for this setting, though the approximation ratio depends on the Thorup-Zwick parameter t. The paper provides falsifiable running-time and approximation guarantees for all results.

major comments (2)
  1. Lemma 16 (Section 6.2): The overcounting bound is stated as N̂(v,r) ≤ (t+1)·|N(v,r)|, justified by the claim that each vertex u ∈ N(v,r) appears in at most t of the clusters C(p_i(v), αr) (one per level i) and at most once in Bunch(v). The 'at most one cluster per level' claim is not explicitly justified. A vertex u could in principle belong to C(p_i(v), αr) and C(p_j(v), αr) for i ≠ j whenever dist(u, p_i(v)) < αr and dist(u, p_j(v)) < αr. The Thorup-Zwick cluster C(w) for w ∈ A_i is defined as {v : dist(v,w) < dist(v, A_{i+1})}, and the bunch-cluster duality (Lemma 13) does not by itself limit the number of pivots of v (across levels) that have u in their cluster. If a vertex can appear in Θ(t) clusters across levels (rather than at most one per level), the overcounting factor becomes Θ(t²) instead of (t+1), which would change ρ from t+1 to Θ(t²) and affect the approximation ratio of O
  2. Theorem 1.2 (Section B.1): The success probability stated in the theorem is (1−t/n)·(ε/⌈(1+ε)⌉)^{k−1}, but Lemma 24 states (1−γ)·(ε/⌈(1+ε)⌉)^{k−1} where γ = t/n. These are consistent, but Lemma 19 states the probability as (1−γ)(1/(1+ε)t)^{k−1}, which appears to be a different expression. Please reconcile the probability statements across Theorem 1.2, Lemma 19, and Lemma 24.
minor comments (6)
  1. Title: 'Deterministick-Clustering' should be 'Deterministic k-Clustering' (missing space).
  2. Section 6.1, last paragraph: 'The total preprocessing time is O(mn^{1/c})' should presumably be O(t·m·n^{1/t}) to be consistent with Theorem 12 and Theorem 1.4. Similarly, 'total storage is O(mn^{1/c})' should be O(t·n^{1+1/t}).
  3. Lemma 16 statement: 'ˆN(v,r) ≤ (t+1)·|N(v,αr)|' uses αr on the right-hand side, but the surrounding text (Equation (5) and the paragraph before Lemma 15) discusses N(v,r). Please clarify whether the bound is with respect to |N(v,r)| or |N(v,αr)|.
  4. Section 5.1.1: The argument that the forbidding loop correctly simulates Algorithm 2 relies on the claim that if v ∈ N̂ but v ∉ V_touched, then v's ball was already forbidden. This is correct but stated briefly; a sentence explaining that δ_s(v) was already ≤ (1+ε)·100c⁴·r before the current insertion would improve clarity.
  5. Table 1: The footnote markers (†, ‡, *) are defined, but the green highlighting for new results is mentioned in the caption but not visible in the text format. Consider adding explicit markers.
  6. Lemma 14 is cited as coming from [54] (Thorup-Zwick compact routing), while the main distance oracle reference is [55]. Please verify this attribution is correct.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the two specific comments. Below we address each point. For Comment 1, we explain why the (t+1) bound in Lemma 16 is correct—the key observation is that there is exactly one pivot per level, hence at most one cluster per level—but we agree the proof lacks this justification and will revise it. For Comment 2, we confirm that Lemma 19 contains a typo and will fix it.

read point-by-point responses

  1. Referee: Lemma 16 (Section 6.2): The overcounting bound is stated as N̂(v,r) ≤ (t+1)·|N(v,r)|, justified by the claim that each vertex u ∈ N(v,r) appears in at most t of the clusters C(p_i(v), αr) (one per level i) and at most once in Bunch(v). The 'at most one cluster per level' claim is not explicitly justified. A vertex u could in principle belong to C(p_i(v), αr) and C(p_j(v), αr) for i ≠ j whenever dist(u, p_i(v)) < αr and dist(u, p_j(v)) < αr. The Thorup-Zwick cluster C(w) for w ∈ A_i is defined as {v : dist(v,w) < dist(v, A_{i+1})}, and the bunch-cluster duality (Lemma 13) does not by itself limit the number of pivots of v (across levels) that have u in their cluster. If a vertex can appear in Θ(t) clusters across levels (rather than at most one per level), the overcounting factor becomes Θ(t²) instead of (t+1), which would change ρ from t+1 to Θ(t²) and affect the approximation ratio of O

    Authors: We thank the referee for raising this point. After careful review, we confirm that the bound N̂(v,r) ≤ (t+1)·|N(v,r)| in Lemma 16 is correct, but we agree that the proof does not explicitly justify the key claim. We will revise the proof to include the missing argument, which is as follows. revision: partial

  2. Referee: Theorem 1.2 (Section B.1): The success probability stated in the theorem is (1−t/n)·(ε/⌈(1+ε)⌉)^{k−1}, but Lemma 24 states (1−γ)·(ε/⌈(1+ε)⌉)^{k−1} where γ = t/n. These are consistent, but Lemma 19 states the probability as (1−γ)(1/(1+ε)t)^{k−1}, which appears to be a different expression. Please reconcile the probability statements across Theorem 1.2, Lemma 19, and Lemma 24.

    Authors: The referee is correct that Lemma 19 contains a typographical error. The probability expression in Lemma 19 should read (1−γ)·(ε/⌈(1+ε)⌉)^{k−1}, matching Lemma 24 and Theorem 1.2. The expression (1/(1+ε)t)^{k−1} appearing in Lemma 19 is a typo; it does not reflect the actual bound proved in Lemma 23 and used in Lemma 24. We will correct Lemma 19 to ensure consistency across all three statements. revision: yes

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity found; the paper combines independently published external tools in new ways.

full rationale

The paper's four main results (Theorems 1.1–1.4) are obtained by combining externally published, independently authored tools: Gonzalez's greedy k-center framework [27], the Source-Insertion SSSP data structure of Górkiewicz and Karczmarz [28], the greedy (k,z)-clustering template of Dupré la Tour and Saulpic [43], Cohen's ball-size estimation [17], and the Thorup–Zwick distance oracle [55]. None of these cited works are authored by the present paper's authors, so there is no self-citation chain. For each result, the paper verifies that its implementation satisfies the abstract conditions required by the external framework: (a) for Theorem 1.1, Lemma 3.1 gives a self-contained proof that the (2+ε) guarantee follows from the standard Gonzalez packing argument using the (1+ε)-approximate distances maintained by [28]; (b) for Theorem 1.3, Section 5.1.1 checks that the ball-values, approximate balls, and forbidding loop all satisfy the same inequalities (Equations (1) and (2)) required by Algorithm 2 of [43], with no additional approximation loss; (c) for Theorem 1.4, Lemmas 15–16 show that the Thorup–Zwick-based construction N̂(v,r) satisfies Equation (1) with ρ = t+1, which then plugs into the generalized analysis of [43]'s Appendix A. No 'prediction' or 'first-principles result' reduces to its inputs by construction. The running-time bounds follow from the stated update-time guarantees of [28] and the preprocessing time of [55], both of which are externally verifiable results. The score of 1 (rather than 0) reflects that the paper's correctness is contingent on the correctness of [28] and [43], but this is normal dependency on external results, not circularity.

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

The paper introduces no new entities, particles, forces, or postulated objects. All data structures and frameworks are drawn from prior literature. The free parameters (ε, c, ρ, t, z) are standard algorithmic parameters controlling approximation-quality vs. running-time tradeoffs, not values fitted to experimental data. The axioms are all external published results that serve as black-box tools.

free parameters (5)
  • ε = user-specified, (0,1]
    Accuracy parameter controlling the approximation factor and running time tradeoff. Not fitted to data but chosen by the user.
  • c = ≥5 (randomized); Θ(t²) (deterministic)
    Template parameter from [43] controlling radius blowup in approximate balls. Set to max(8t-4, (t+1)²/2, 5) in the deterministic case.
  • ρ = 3 (randomized); t+1 (deterministic)
    Slack parameter for ball values (Equation 1). Not fitted but set based on the ball-size estimation method used.
  • t (Thorup-Zwick levels) = user-specified integer ≥1
    Controls the tradeoff between approximation quality O(poly(t)) and running time Õ(t·m·n^{1/t}) in Theorem 1.4.
  • z = constant ≥1
    Exponent in the (k,z)-clustering objective (z=1 for k-median, z=2 for k-means). Input parameter, not fitted.
assumptions (5)
  • domain assumption Source-Insertion SSSP data structure (Lemma 1, from [28]): maintains (1+ε)-approximate distances under source-edge insertions in Õ(m) total update time.
    All four results depend on this external data structure. Cited from Górkiewicz and Karczmarz [ICALP 2025]. Used in Sections 3, 5, 6, and Appendix B.
  • domain assumption Greedy (k,z)-clustering framework of Dupré la Tour and Saulpic [43] (Algorithm 2) yields O(1)-approximation when ball values satisfy Equation (1) and approximate balls satisfy Equation (2).
    The randomized and deterministic (k,z)-clustering results instantiate this template. The approximation guarantee is inherited from [43]. Used in Sections 4, 5, 6.
  • domain assumption Cohen's ball-size estimation [17] (Lemma 28) provides (1±ε)-approximate ball sizes with O(log log n) query time.
    Used for the randomized (k,z)-clustering algorithm in Section 5. External result from Cohen [JCSS 1997].
  • domain assumption Thorup-Zwick distance oracle [55] (Theorem 12): computes hierarchy, pivots, bunches, and clusters in Õ(t·m·n^{1/t}) time with O(t·n^{1/t}) bunch size.
    Used for the deterministic (k,z)-clustering algorithm in Section 6. External result from Thorup and Zwick [JACM 2005].
  • domain assumption The vertex-touch reporting property (Lemma 3, from [28]): the SSSP structure reports exactly the vertices whose distance estimates decrease, with total size Õ(m) over O(n) insertions.
    Critical for the running time analysis of the forbidding loop in Section 5 and the k-center algorithm in Section 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Randomized and Deterministic k-Clustering on Graphs." pith.science (2026). https://pith.science/paper/RK2ZB6FS

@misc{pith2026260707615,
  author       = {Pith},
  title        = {Pith review of: Faster Randomized and Deterministic k-Clustering on Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RK2ZB6FS}},
  note         = {Machine review of arXiv:2607.07615}
}
abstract

In this paper, we study the $(k,z)$-clustering and $k$-center problems on graphs, where $(k,z)$-clustering generalizes the $k$-median ($z=1$) and $k$-means ($z=2$) problems. We obtain the following main results. Our first contribution is the first deterministic algorithm for $k$-center on graphs that achieves a $(2+\varepsilon)$-approximation in $\tilde{O}(m)$ time. This affirmatively resolves an open problem raised by Abboud, Cohen-Addad, Lee, and Manurangsi [SOSA 2023]. Our techniques also extend to the $k$-center with outliers problem, where up to $t$ points may be discarded. Our second contribution is a randomized algorithm for $(k,z)$-clustering on graphs that achieves an $O(1)$-approximation in $\tilde{O}(m)$ time, which in particular covers $k$-median ($z=1$) and $k$-means ($z=2$). Prior to this work, an $\tilde{O}(m)$-time randomized algorithm was known for $k$-median by Thorup [SIAM J. Comput. 2005], and a recent work of Jiang, Jin, Lou, and Lu [2026] achieves $m^{1+o(1)}$ time for general $z$ via local search. Finally, we design a deterministic algorithm for $(k,z)$-clustering on graphs that achieves an $O(\mathrm{poly}(c))$-approximation in $\tilde{O}(m^{1+1/c})$ time, for a positive parameter $c$. To obtain this result, we use techniques from the Thorup-Zwick distance oracle [JACM 2005]; this technical connection may be of independent interest, considering the wide application of distance oracles in various computational settings. Most of our algorithms are incremental, in the sense that for any given parameter $k$, they return a sequence of centers such that every prefix of length $\ell \leq k$ yields a constant-factor approximate solution to the $\ell$-clustering problem.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages

  1. [28]

    On incremental approximate shortest paths in directed graphs

    Adam Górkiewicz and Adam Karczmarz. On incremental approximate shortest paths in directed graphs. In52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 93–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025

    work page 2025

  2. [41]

    Local search for clustering in almost-linear time

    Shaofeng H-C Jiang, Yaonan Jin, Jianing Lou, and Pinyan Lu. Local search for clustering in almost-linear time. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5960–5977. SIAM, 2026

    work page 2026

  3. [43]

    Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means

    Max Dupré la Tour and David Saulpic. Faster and simpler greedy algorithm fork-median and k-means, 2025. To appear in ICALP 2026. URL:https://arxiv.org/abs/2407.11217, arXiv:2407.11217

    work page Pith review arXiv 2025

  4. [1]

    On the fine- grained complexity of approximating k-center in sparse graphs

    Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi. On the fine- grained complexity of approximating k-center in sparse graphs. InSymposium on Simplicity in Algorithms (SOSA), pages 145–155. SIAM, 2023

    work page 2023

  5. [2]

    Aggarwal and Chandan K

    Charu C. Aggarwal and Chandan K. Reddy, editors.Data Clustering: Algorithms and Applica- tions. CRC Press, 2014

    work page 2014

  6. [3]

    Better Guarantees for k-Means and

    Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms.SIAM J. Comput., 49(4), 2020. doi:10.1137/18M1171321

    work page doi:10.1137/18m1171321 2020

  7. [4]

    Euclidean spanners: short, thin, and lanky

    Sunil Arya, Gautam Das, David M Mount, Jeffrey S Salowe, and Michiel Smid. Euclidean spanners: short, thin, and lanky. InProceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 489–498, 1995

    work page 1995

  8. [5]

    Approximateclusteringviacore-sets

    MihaiBadoiu, SarielHar-Peled, andPiotrIndyk. Approximateclusteringviacore-sets. InJohnH. Reif, editor,Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 250–257. ACM, 2002.doi:10.1145/509907.509947

    work page doi:10.1145/509907.509947 2002

Show all 61 references
  1. [6]

    Probabilistic approximations of metric spaces and its algorithmic applications

    Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14-16 October, 1996, pages 184–193. IEEE Computer Society, 1996.doi: 10.1109/SFCS.1996.548477

    1996 doi

  2. [7]

    Optimal fully dynamick-center clustering for adaptive and oblivious adversaries

    MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamick-center clustering for adaptive and oblivious adversaries. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedin...

    2023 doi

  3. [8]

    A survey of clustering data mining techniques

    Pavel Berkhin. A survey of clustering data mining techniques. In Jacob Kogan, Charles K. Nicholas, and Marc Teboulle, editors,Grouping Multidimensional Data - Recent Advances in Clustering, pages 25–71. Springer, 2006.doi:10.1007/3-540-28349-8\_2

    2006 doi

  4. [9]

    An improved approximation fork-median and positive correlation in budgeted optimization

    Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation fork-median and positive correlation in budgeted optimization. In ACM Transactions on Algorithms, volume 13, 2017

    2017

  5. [10]

    Rounding via trees: Deterministic approximation algorithms for group steiner trees andk-median

    Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha. Rounding via trees: Deterministic approximation algorithms for group steiner trees andk-median. In Jeffrey Scott Vitter, editor,Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas,...

    1998 doi

  6. [11]

    An improved greedy approximation for (metric) k-means

    Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland. An improved greedy approximation for (metric) k-means. In66th 22 IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2...

    2025 doi

  7. [12]

    Improved combinatorial algorithms for facility location problems.SIAM J

    Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for facility location problems.SIAM J. Comput., 34(4):803–824, 2005.doi:10.1137/S0097539701398594

    2005 doi

  8. [13]

    Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approxi- mation algorithm for the k-median problem.J. Comput. Syst. Sci., 65(1):129–149, 2002. URL: https://doi.org/10.1006/jcss.2002.1882,doi:10.1006/JCSS.2002.1882

    2002 doi

  9. [14]

    Mount, and Giri Narasimhan

    Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. InSODA, pages 642–651, 2001

    2001

  10. [15]

    A dependent lp-rounding approach for the k-median problem

    Moses Charikar and Shi Li. A dependent lp-rounding approach for the k-median problem. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors,Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012,...

    2012 doi

  11. [16]

    On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications.SIAM J

    Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications.SIAM J. Comput., 39(3):923–947, 2009.doi:10.1137/070699007

    2009 doi

  12. [17]

    Size-estimation framework with applications to transitive closure and reachability

    Edith Cohen. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55(3):441–453, 1997

    1997

  13. [18]

    All-pairs small-stretch paths.J

    Edith Cohen and Uri Zwick. All-pairs small-stretch paths.J. Algorithms, 38(2):335–353, 2001. URL:https://doi.org/10.1006/jagm.2000.1117,doi:10.1006/JAGM.2000.1117

    2001 doi

  14. [19]

    Breach- ing the 2 LMP approximation barrier for facility location with applications tok-median

    Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn. Breach- ing the 2 LMP approximation barrier for facility location with applications tok-median. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discr...

    2023 doi

  15. [20]

    A (2 +ε)-approximation algorithm for metric k-median

    Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, and Ola Svensson. A (2 +ε)-approximation algorithm for metric k-median. In Michal Koucký and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Pragu...

    2025

  16. [21]

    An improved local search algorithm for k-median

    Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Ale...

    2022 doi

  17. [22]

    Deterministic k-median clustering in near-optimal time

    Martín Costa and Ermiya Farokhnejad. Deterministic k-median clustering in near-optimal time. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 23 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, De...

    2025 doi

  18. [23]

    Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction

    Hu Ding, Haikuo Yu, and Zixiu Wang. Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors,27th Annual European Symposium on Algorithms (ESA 2019), volume 144 ofLeibniz Internationa...

    2019 doi

  19. [24]

    Optimal euclidean spanners: Really short, thin, and lanky.J

    Michael Elkin and Shay Solomon. Optimal euclidean spanners: Really short, thin, and lanky.J. ACM, 62(5):35:1–35:45, 2015.doi:10.1145/2819008

    2015 doi

  20. [25]

    Tomás Feder and Daniel H. Greene. Optimal algorithms for approximate clustering. In Janos Simon, editor,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 434–444. ACM, 1988.doi:10.1145/62212.62255

    1988 doi

  21. [26]

    On strong diameter padded decompositions

    Arnold Filtser. On strong diameter padded decompositions. In22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019, page 6. Schloss Dagstuhl-Leibni...

    2019

  22. [27]

    González

    Teofilo F. González. Clustering to minimize the maximum intercluster distance. InTheoretical Computer Science, volume 38, pages 293–306, 1985

    1985

  23. [29]

    Gowda, Thomas W

    Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, and Khoa Trinh. Improved bi-point rounding algorithms and a golden barrier fork-median. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Floren...

    2023 doi

  24. [30]

    Clustering data streams

    Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan. Clustering data streams. In41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, November 12-14, 2000, pages 359–366. IEEE Computer Society, 2000. doi:10.1109/SFCS...

    doi

  25. [31]

    Simpler analyses of local search algorithms for facility location.CoRR, abs/0809.2554, 2008

    Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location.CoRR, abs/0809.2554, 2008. URL:http://arxiv.org/abs/0809.2554, arXiv: 0809.2554

    2008 arXiv

  26. [32]

    Cluster analysis and mathematical programming.Math

    Pierre Hansen and Brigitte Jaumard. Cluster analysis and mathematical programming.Math. Program., 79:191–215, 1997.doi:10.1007/BF02614317. 24

    1997 doi

  27. [33]

    Clustering motion.Discret

    Sariel Har-Peled. Clustering motion.Discret. Comput. Geom., 31(4):545–565, 2004. URL: https://doi.org/10.1007/s00454-004-2822-7,doi:10.1007/S00454-004-2822-7

    2004 doi

  28. [34]

    Euclidean spanners in high di- mensions

    Sariel Har-Peled, Piotr Indyk, and Anastasios Sidiropoulos. Euclidean spanners in high di- mensions. In Sanjeev Khanna, editor,Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 80...

    2013 doi

  29. [35]

    Hochbaum and David B

    Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for thek-center problem. InMathematics of Operations Research, volume 10, pages 180–184, 1985

    1985

  30. [36]

    Sublinear time algorithms for metric space problems

    Piotr Indyk. Sublinear time algorithms for metric space problems. In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors,Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 428–434....

    1999 doi

  31. [37]

    A. K. Jain, M. N. Murty, and P. J. Flynn. Data clustering: A review.ACM Comput. Surv., 31(3):264–323, 1999.doi:10.1145/331499.331504

    1999 doi

  32. [38]

    Vazirani

    Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP.J. ACM, 50(6):795–824, 2003.doi:10.1145/950620.950621

    2003 doi

  33. [39]

    A new greedy approach for facility location problems

    Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In John H. Reif, editor,Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731–740. ACM, 2002. doi:10.1145/509907.510012

    2002 doi

  34. [40]

    Vazirani

    Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. InJACM, volume 48, pages 274–296, 2001

    2001

  35. [42]

    The price of incrementality in k-center clustering.arXiv preprint arXiv:2606.08713, 2026

    László Kozma. The price of incrementality in k-center clustering.arXiv preprint arXiv:2606.08713, 2026

    2026 arXiv

  36. [44]

    Truly optimal euclidean spanners.SIAM Journal on Computing, 54(4):FOCS19–135, 2025

    Hung Le and Shay Solomon. Truly optimal euclidean spanners.SIAM Journal on Computing, 54(4):FOCS19–135, 2025

    2025

  37. [45]

    Approximating k-median via pseudo-approximation.SIAM J

    Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation.SIAM J. Comput., 45(2):530–547, 2016.doi:10.1137/130938645. 25

    2016 doi

  38. [46]

    Williamson

    Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson. A general approach for incremental approximation and hierarchical clustering.SIAM J. Comput., 39(8):3633–3669, 2010.doi:10.1137/070698257

    2010 doi

  39. [47]

    Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

    Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Leonard J. Schulman, editor,Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages ...

    2010 doi

  40. [48]

    The online median problem.SIAM Journal on Computing, 32(3):816–832, 2003

    Ramgopal R Mettu and C Greg Plaxton. The online median problem.SIAM Journal on Computing, 32(3):816–832, 2003

    2003

  41. [49]

    Mettu and C

    Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering. Mach. Learn., 56(1-3):35–60, 2004. URL: https://doi.org/10.1023/B:MACH.0000033114. 18632.e0,doi:10.1023/B:MACH.0000033114.18632.E0

    2004 doi

  42. [50]

    Deterministic constructions of approximate distance oracles and spanners

    Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. InInternational Colloquium on Automata, Languages, and Programming, pages 261–272. Springer, 2005

    2005

  43. [51]

    On dynamic shortest paths problems.Algorithmica, 61(2):389–401, 2011

    Liam Roditty and Uri Zwick. On dynamic shortest paths problems.Algorithmica, 61(2):389–401, 2011. URL:https://doi.org/10.1007/s00453-010-9401-5, doi:10.1007/ S00453-010-9401-5

    2011 doi

  44. [52]

    Quick k-median, k-center, and facility location for sparse graphs

    Mikkel Thorup. Quick k-median, k-center, and facility location for sparse graphs. InInternational Colloquium on Automata, Languages, and Programming, pages 249–260. Springer, 2001

    2001

  45. [53]

    Quick k-median, k-center, and facility location for sparse graphs.SIAM Journal on Computing, 34(2):405–432, 2005

    Mikkel Thorup. Quick k-median, k-center, and facility location for sparse graphs.SIAM Journal on Computing, 34(2):405–432, 2005

    2005

  46. [54]

    Compact routing schemes

    Mikkel Thorup and Uri Zwick. Compact routing schemes. InProceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, pages 1–10, 2001

    2001

  47. [55]

    Approximate distance oracles.Journal of the ACM (JACM), 52(1):1–24, 2005

    Mikkel Thorup and Uri Zwick. Approximate distance oracles.Journal of the ACM (JACM), 52(1):1–24, 2005

    2005

  48. [56]

    A tutorial on spectral clustering.Stat

    Ulrike von Luxburg. A tutorial on spectral clustering.Stat. Comput., 17(4):395–416, 2007. URL:https://doi.org/10.1007/s11222-007-9033-z,doi:10.1007/S11222-007-9033-Z

    2007 doi

  49. [57]

    Shmoys.The Design of Approximation Algorithms

    DavidP.Williamson and DavidB. Shmoys.The Design of Approximation Algorithms. Cambridge University Press, 2011. 26 Appendix A Approximation ofValue(·,·) Thestatic( k, z)-clusteringalgorithmofDuprelaTourandSaulpic[ 43]definesafunction Value(B(u, r)) which satisfies the following...

    2011

  50. [58]

    In turn, the constraint onc becomes c≥ ρ2 2 instead ofc≥5

    The first lemma that should be adjusted is Lemma A.1 in [43], where within its proof, the constant3can be trivially replaced by the parameterρ. In turn, the constraint onc becomes c≥ ρ2 2 instead ofc≥5

  51. [59]

    When cost(In(Pγ), Ck)is analyzed in the proof of Lemma A.5, the constant3can be trivially replaced by ρ, since (rγ)z · |B(γ, r γ)| ≤ρ·Value(B(γ, r γ))

    The second lemma that should be adjusted is Lemma A.5 in [43]. When cost(In(Pγ), Ck)is analyzed in the proof of Lemma A.5, the constant3can be trivially replaced by ρ, since (rγ)z · |B(γ, r γ)| ≤ρ·Value(B(γ, r γ))

  52. [60]

    When cost(B(x, c·r ), Γ) is analyzed in the proof of Lemma A.6, the constant3can be trivially replaced byρ, since rz · |B(x, c·r)| ≥ Value(B(x,r)) ρ

    The third lemma that should be adjusted is Lemma A.6 in [43]. When cost(B(x, c·r ), Γ) is analyzed in the proof of Lemma A.6, the constant3can be trivially replaced byρ, since rz · |B(x, c·r)| ≥ Value(B(x,r)) ρ

  53. [61]

    Bk-Center with Outliers We now extend the incremental framework developed in Section 3 to thek-center problem with outliers, where up tot points may be discarded

    Finally, by combining Lemmas A.5 and A.6 at the end of Appendix A in [43], the extraρ2 factor arises in the approximation ratio. Bk-Center with Outliers We now extend the incremental framework developed in Section 3 to thek-center problem with outliers, where up tot points may...

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.