Pith. sign in

REVIEW 3 major objections 6 minor 47 references

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs

T0 review · 3 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read RS-k-means++ replaces the exact D2-sampling step of k-means++ by a rejection loop, preserving the $O(\log k)$ guarantee and improving the additive variance error from $O(1/m)$ to $k^{-\Omega(m/\beta)} \Delta_1(X)$.

desk verdict Good new analysis of perturbed k-means++, but the main theorem substitutes a random oversampling ratio by its expectation without concentration, so the exponential trade-off is not yet proven. read the letter →

arxiv 2502.02085 v1 pith:H3SHDKWN submitted 2025-02-04 cs.DS cs.LG

Poojan Shah , Shashwat Agrawal , Ragesh Jaiswal This is my paper · ORCID
classification cs.DScs.LG MSC 68W2068W2562H30
keywords k-means++D2-samplingrejectionsamplingclusteringsublinear-timealgorithmsrandomizedapproximationdata-dependentparametersample-and-querydatastructure
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

k-means++ picks cluster seeds by D2-sampling, where each new center is chosen with probability proportional to its distance from the centers already chosen, but the step costs $O(nkd)$ time. This paper claims that the same sampling can be done by rejection sampling from a much cheaper proposal distribution, concentrated on squared distances from the first random center, with a uniform fallback when rejection does not finish quickly. The central result is a trade-off: with an unlimited round budget, RS-k-means++ keeps the $O(\log k)$ competitive guarantee of k-means++ and runs in $\tilde{O}(\mathrm{nnz}(X) + \beta k^2 d \log(k/\epsilon))$ time with high probability, and with a bounded budget of $m' = c m \ln k$ rounds per center the additional cost over the $O(\log k)$ guarantee is only $k^{-\Omega(m/\beta)} \Delta_1(X)$ rather than the $O(1/m) \Delta_1(X)$ penalty of the earlier Metropolis-Hastings-based seeding. If the data-dependent ratio $\beta = \mathbb{E}[\Delta_1(X)/\Delta_k(X)]$ is moderate, this makes near-k-means++-quality seeding sublinear per clustering after a one-time sparse preprocessing pass.

What carries the argument

The load-bearing object is the oversampling ratio $\tau$ and the rejection loop built around it: each round draws from the squared-norm-plus-first-center proposal and accepts with probability $\rho(x) = D_1(x)/(\tau D_2(x))$, where $D_1(x) = \Delta(x,S)/\Delta(X,S)$ is the D2 distribution, which makes the accepted sample exactly D2-distributed and makes the round count geometric with expectation $\tau$. A complete binary tree storing squared norms supplies the proposal samples in $O(\log n)$ time after $O(\mathrm{nnz}(X))$ preprocessing, so no estimate of $\tau$ or $\beta$ is ever needed. The proof machinery is the $\delta$-k-means++ analysis, which tracks how the uniform fallback contaminates the standard k-means++ potential argument: the potential $W_t/|U_t|\Delta_t(U_t)$ bounds the uncovered-cluster cost while a fresh term $(6k\delta/(1-\delta))\Delta_1(X)$ records the cost of wasted rejection rounds.

What would settle it

Fix a dataset with one dense cluster near the origin and one distant point, set $k=2$, and run RS-k-means++$(\mathcal{X}, k, cm\ln k)$ many times, recording how often the rejection loop exhausts its budget and falls back to uniform sampling. If the empirical fallback fraction is substantially larger than $e^{-m/\beta}$ for any fixed $m$, the claimed probabilistic control on the additive error fails; equivalently, measuring the tail of the per-center rejection round count across seeds should be compared against a geometric distribution with parameter at least $1/(4\beta)$.

Watch

Extended reading notes

Core claim

The paper's central discovery is an oversampling identity that turns D2 sampling into a geometric rejection loop. For any center set $S$ containing the first uniformly random center $c_1$, the D2 weight of every point $x$ is at most $\tau$ times the weight of the proposal distribution $D_2(x) = (\|x\|^2 + \|c_1\|^2)/(\|X\|^2 + n\|c_1\|^2)$, with $\tau = 2(\|X\|^2 + n\|c_1\|^2)/\Delta(X,S)$ and $\mathbb{E}[\tau] \le 4\Delta_1(X)/\Delta_k(X)$. Running the rejection loop without a round limit yields a D2 sample in $O(\beta k^2 d \log(k/\epsilon))$ time with probability at least $1 - \epsilon$ after $\tilde{O}(\mathrm{nnz}(X))$ preprocessing; running it for $m' = c m \ln k$ rounds per center gives centers $S$ with $\mathbb{E}[\Delta(X,S)] \le 8(\ln k + 2)\Delta_k(X) + (6k/(k^{cm/(2\beta(X))} - 1))\Delta_1(X)$. The proof proceeds through a perturbed variant, $\delta$-k-means++, which samples from $(1-\delta)D_2 + \delta\,\mathrm{Uniform}$, and the additive variance term is exactly the price of the uniform fallback when rejection exceeds its budget.

Load-bearing premise

The proofs control only the expected value of the oversampling ratio $\tau$, not its tail behavior, so the high-probability runtime and fallback-probability bounds are stated in terms of $\beta = \mathbb{E}[\Delta_1(X)/\Delta_k(X)]$ without showing that actual runs stay close to this expectation.

Editorial extensions

If this is right

  • With an unlimited rejection budget, RS-k-means++ matches the $O(\log k)$ competitive guarantee of k-means++ in expectation while spending only $O(\beta k^2 d \log(k/\epsilon))$ time per clustering after $\tilde{O}(\mathrm{nnz}(X))$ preprocessing, with no externally supplied estimate of $\beta$.
  • With $m' = c m \ln k$ rounds per center, the additive variance penalty shrinks as $k^{-\Omega(m/\beta)} \Delta_1(X)$, an exponential improvement over the $O(1/m)\Delta_1(X)$ penalty of the previous AF-k-MC2 algorithm at the same order of runtime.
  • Since rejection rounds are independent, running the loop on $M$ parallel cores raises the per-round success probability to at least $1 - e^{-pM}$ and cuts the expected number of rounds to at most $e^{pM}/(e^{pM}-1)$, where $p \ge 1/(2\beta)$.
  • The sample-and-query binary tree supports point updates in $O(\log n)$ time, so the fast sampling structure can be maintained incrementally as the dataset changes rather than rebuilt.
  • On the datasets tested, the measured $\beta$ values lay between about 1.9 and 9.7, and the bounded-budget version approached k-means++ solution quality rapidly while running tens of times faster than the Markov-chain baseline on large sparse data.

Reading between the lines

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

  • An explicit concentration bound for the oversampling ratio $\tau$ would let the high-probability runtime and fallback-probability claims be stated without the expectation caveat, and would identify the worst-case datasets where the current bounds degrade.
  • The $\delta$-k-means++ analysis is a general template for any approximate D2 sampler whose proposal is a small uniform mixture, so the same additive-variance argument could transfer to coreset-based or streaming seeding pipelines.
  • The practical regime is datasets with $n$ much larger than $k$ and moderate variance ratio; an adaptive version that grows the round budget whenever observed rejection counts are high would extend the method to less benign distributions without knowing $\beta$ in advance.
  • A testable extension is to replace the uniform fallback with a cheaper data-dependent distribution, which would shrink the $\Delta_1(X)$ additive term while keeping the same exponential decay in $m$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper proposes RS-k-means++, a rejection-sampling-based acceleration of k-means++ seeding. A preprocessing step builds a binary-tree data structure for sampling from the distribution D2(x) ∝ ||x||² (after implicit centering), from which the k-means++ D2-sampling distribution is obtained by rejection sampling. Two variants are analyzed: an unbounded-rounds version that recovers the exact k-means++ guarantee, and a bounded-rounds version that trades solution quality for speed. The main claimed contribution (Theorem 2.1) is that with m' = O(m log k) rounds per sampling step, the expected cost is 8(ln k+2)Δ_k + O(k^{1−Ω(m/β)}) Δ_1, an exponential improvement over Bachem et al.'s O(1/m) additive term at a similar runtime. The analysis introduces a δ-k-means++ abstraction in which each sample is drawn from a mixture of the D2-distribution and the uniform distribution, and proves a potential-based approximation guarantee for this abstraction (Theorem 5.1).

Significance. If the main theorem were established, the exponential trade-off would be a genuine improvement over prior sublinear-time k-means++ results, and the rejection-sampling framework is simple, parallel-friendly, and empirically effective. The potential-based analysis of the δ-k-means++ variant (Theorem 5.1) is a solid technical contribution and appears structurally sound. The paper also provides reproducible experimental code and reports substantial speedups on real datasets. However, the connection between the actual random rejection-sampling process and the deterministic δ-k-means++ model is not rigorously made, and this gap affects the paper's central theorem and the stated high-probability runtime claims.

major comments (3)
  1. [§4.1, Corollaries 4.6–4.7 and Theorem 2.1] The analysis replaces the random oversampling ratio τ of Lemma 4.5 by the parameter β using only the bound E[τ] ≤ 4β, but Lemmas 4.2 and 4.4 provide tail and mixing bounds only for a fixed τ. For random τ, Lemma 4.4 gives δ = Pr[T > m'] ≤ E[e^{-m'/τ}], and E[τ] ≤ 4β does not imply E[e^{-m'/τ}] ≤ e^{-m'/(4β)}; for instance, with β = 1 and τ = 4 or 5 each with probability 1/2, E[e^{-10/τ}] ≈ 0.1087 > e^{-10/4.5} ≈ 0.1084. Moreover, in RS-k-means++ the mixing probability δ_t at step t is random and history-dependent, while Theorem 4.8 applies to a fixed deterministic δ; no bound on E[δ_t/(1−δ_t)] is given. Consequently, the substitution δ = k^{-cm/(2β)} in Theorem 2.1 is not justified, and the claimed exponential improvement k^{−Ω(m/β)} is not established by the provided proof. A repair would require a concentration bound on τ or a direct bound on the expected distortion of the mixing probability.
  2. [§4.1, Corollary 4.7] The statement that Procedure 3 with input (X, S, m log t) outputs a sample from (1−δ)D2 + δU with δ ≤ e^{-m/β} is numerically inconsistent with Lemma 4.4, which gives δ ≤ e^{-m log t/τ} for the realized τ; even under a pointwise bound τ ≤ β, this is e^{-m log t/β}, not e^{-m/β}. In addition, the exponent in Theorem 2.1 has a factor-2 mismatch with the bound E[τ] ≤ 4β proved in Corollary 4.6: with m' = c m ln k rounds, the best bound directly from Lemma 4.4 would be k^{-c m/τ}, which is k^{-c m/(4β)} if τ were pointwise bounded by 4β, whereas Theorem 2.1 states k^{-c m/(2β)}. These quantitative gaps must be reconciled in a revision.
  3. [§4.1, Corollary 4.6 and Theorem 2.2] The high-probability runtime bound in Corollary 4.6—O(β(X)(td + log n) log(1/ε)) with probability at least 1−ε—is not a consequence of the proof, which establishes only the expectation E[T] = E[τ] ≤ 4β for the number of rejection-sampling rounds T. A tail bound on T would require control of the tail of τ, e.g., P[τ > t], which is absent; τ can be large on a low-probability event while E[τ] remains O(β). Since Theorem 2.2 explicitly states a high-probability cost bound, that theorem is currently unproven as stated. The authors should either supply the missing concentration argument or rephrase the guarantee as an expected-time bound.
minor comments (6)
  1. [§2 (Abstract and Theorem 2.2)] The abstract states that the first method runs in time O~(nnz(X) + βk²d) without specifying whether this is an expectation or a high-probability bound; the theorem and corollary should be consistent on this point.
  2. [§4.2, Procedure preprocess(X)] The preprocessing step "perform x ← x − µ(X) for every x ∈ X" would densify the dataset and make the O(nnz(X)) claim invalid if executed literally. The O(nnz) preprocessing bound holds only if centering is done implicitly, e.g., by storing µ separately and computing norms and inner products on the fly; the text should clarify this.
  3. [§2.2 (data structure space)] Lemma 4.9 (from Tang 2019) states O(ν log n) space, but the discussion in Section 2.2 says the data structure takes "only O(nnz(X)) additional space"; since n ≤ nnz(X) for datasets with no zero points this is essentially true up to constants, but the discrepancy should be noted.
  4. [§5.1, Lemma 5.9] In the proof of Lemma 5.9, the second term of the final bound has 2t/((1−δ)max(1,k−t−1)²) inside the δ-multiplied sum, but in the bound just below it is simplified as 2t/max(...)² without the (1−δ) denominator; since δ < 1/2 this only affects constants, but the simplification should be justified or corrected.
  5. [§6 (Experiments)] The estimates of β in Table 2 are computed using the cost of RS-k-means++(·,·,∞), which is a random variable and may underestimate the true β; a brief note on how these estimates were averaged would improve reproducibility.
  6. [General presentation] There are several typographical and minor language issues: Algorithm 7 says "Chose a point x" instead of "Choose a point x"; "cauchy-schwarz inequality" should be capitalized; and in the proof of Corollary 4.6, "where the last inequality follows" should be "where the last equality/inequality follows" (the step is an equality).

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the central trade-off is not equivalent to its inputs; the only self-citation is non-load-bearing, and the main proof gap is a correctness issue, not circularity.

full rationale

The derivation chain for the main theorem is self-contained. Lemma 4.5 establishes that the proposal distribution tau-oversamples the D2 distribution via Cauchy-Schwarz; Lemma 4.4 converts the oversampling factor into the perturbation probability delta <= e^{-m/tau}; Theorem 5.1, proved via the potential argument and the external Arthur-Vassilvitskii lemma, gives E[Delta] <= 8(ln k + 2) Delta_k + 6k delta/(1 - delta) Delta_1. At no point is the target bound inserted into the proof. The data-dependent parameter beta(X) is defined through Delta_1(X)/Delta_k(X), and the stated E[beta(X)] = Delta_1(X)/Delta_k(X) follows from the uniform first center and centering; it is not fitted from the algorithm's output. The only self-citation, Jaiswal and Shah (2024), appears in Section 2.3 merely to note a similar sampling data structure and is never used to prove Theorem 2.1 or Theorem 2.2. The reviewer concern that delta <= e^{-m/beta(X)} is obtained from E[tau] <= 4 beta without a concentration bound is a genuine proof gap about expectation versus pointwise control, but it is not circularity: the claimed exponential factor is not defined to be whatever the proof produces, and the derivation does not assume the theorem it is trying to prove. The paper's own caveats that beta can be unbounded or that Bachem et al.'s analysis needs NP-hard-to-check assumptions are limitations, not circular reductions. Accordingly, no circular step is exhibited; the score of 2 reflects only the presence of one minor, non-load-bearing self-citation.

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

The central claim relies on no fitted constants. The algorithm's only input is m (the rejection-sampling budget, possibly infinite); beta(X) is a defined property of the data set, not an estimated or fitted quantity. The proof uses standard constants from Arthur-Vassilvitskii and Dasgupta. The main unstated reliance is the concentration of the oversampling ratio tau around its expectation, listed under axioms.

assumptions (5)
  • standard math Cauchy-Schwarz inequality gives Delta(x,S) <= 2(||x||^2 + ||c1||^2) for the first center c1 and any x.
    Used in Lemma 4.5 to show the distribution D2(x) = (||x||^2 + ||c1||^2)/(||X||^2 + |X| ||c1||^2) tau-oversamples the D2 distribution, which is the basis of the rejection sampling conversion.
  • standard math Arthur & Vassilvitskii (2007), Lemma 3.1: for z chosen uniformly at random from P, E[Delta(P,z)] = 2 Delta(P, mu(P)).
    Used in Lemma 5.6 and elsewhere to bound E[Delta_t(X)] <= 2 Delta_1(X) for the delta-k-means++ analysis.
  • standard math Arthur & Vassilvitskii (2007), Lemma 3.2: the expected one-step cost of a cluster under D2-sampling is at most 8 Delta(C_i, mu(C_i)).
    Invoked in Lemma 5.5 as the first term of the bound, with an additive delta-dependent term added.
  • ad hoc to paper The oversampling ratio tau = 2(||X||^2 + |X| ||c1||^2)/Delta(X,S) is concentrated enough around its expectation that the failure bound delta <= e^{-m/tau} can be replaced by delta <= e^{-m/beta} in the stated guarantees.
    Corollaries 4.6 and 4.7 state 'with probability at least 1-epsilon' bounds in terms of beta with E[beta] = Delta_1/Delta_k, but the proofs only establish E[tau] <= 4 beta; no concentration or high-probability bound on tau is given. This is the load-bearing gap in the theorem statements.
  • domain assumption The data-dependent parameter beta(X) = Delta_1(X)/Delta_k(X) is bounded (e.g., O(k)) for the datasets of interest.
    Section 3.1 notes beta is unbounded for adversarial data (e.g., |X| = k); sublinear runtime and the improved trade-off only materialize when beta is moderate. The paper argues beta in O(k) for common distributions, citing Bachem et al. 2016b.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs." pith.science (2026). https://pith.science/paper/H3SHDKWN

@misc{pith2026250202085,
  author       = {Pith},
  title        = {Pith review of: A New Rejection Sampling Approach to $k$-$\mathttmeans$++ With Improved Trade-Offs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H3SHDKWN}},
  note         = {Machine review of arXiv:2502.02085}
}
abstract

The $k$-$\mathtt{means}$++ seeding algorithm (Arthur & Vassilvitskii, 2007) is widely used in practice for the $k$-means clustering problem where the goal is to cluster a dataset $\mathcal{X} \subset \mathbb{R} ^d$ into $k$ clusters. The popularity of this algorithm is due to its simplicity and provable guarantee of being $O(\log k)$ competitive with the optimal solution in expectation. However, its running time is $O(|\mathcal{X}|kd)$, making it expensive for large datasets. In this work, we present a simple and effective rejection sampling based approach for speeding up $k$-$\mathtt{means}$++. Our first method runs in time $\tilde{O}(\mathtt{nnz} (\mathcal{X}) + \beta k^2d)$ while still being $O(\log k )$ competitive in expectation. Here, $\beta$ is a parameter which is the ratio of the variance of the dataset to the optimal $k$-$\mathtt{means}$ cost in expectation and $\tilde{O}$ hides logarithmic factors in $k$ and $|\mathcal{X}|$. Our second method presents a new trade-off between computational cost and solution quality. It incurs an additional scale-invariant factor of $ k^{-\Omega( m/\beta)} \operatorname{Var} (\mathcal{X})$ in addition to the $O(\log k)$ guarantee of $k$-$\mathtt{means}$++ improving upon a result of (Bachem et al, 2016a) who get an additional factor of $m^{-1}\operatorname{Var}(\mathcal{X})$ while still running in time $\tilde{O}(\mathtt{nnz}(\mathcal{X}) + mk^2d)$. We perform extensive empirical evaluations to validate our theoretical results and to show the effectiveness of our approach on real datasets.

Figures

Figures reproduced from arXiv: 2502.02085 by the authors.

Figure 1
Figure 1. Data structure for sampling from a vector [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Trade-off plots 19 [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 42 canonical work pages

  1. [1]

    R., M\" a rtens, M., Raupach, C., Swierkot, K., Lammersen, C., and Sohler, C

    Ackermann, M. R., M\" a rtens, M., Raupach, C., Swierkot, K., Lammersen, C., and Sohler, C. (2012). Streamkm++: A clustering algorithm for data streams. ACM J. Exp. Algorithmics , 17

    work page 2012

  2. [2]

    Ahmadian, S., Norouzi-Fard, A., Svensson, O., and Ward, J. (2020). Better guarantees for \ k\ -means and euclidean \ k\ -median by primal-dual algorithms. SIAM Journal on Computing , 49(4):FOCS17--97--FOCS17--156

    work page 2020

  3. [3]

    Ailon, N., Jaiswal, R., and Monteleoni, C. (2009). Streaming k-means approximation. In Bengio, Y., Schuurmans, D., Lafferty, J., Williams, C., and Culotta, A., editors, Advances in Neural Information Processing Systems , volume 22. Curran Associates, Inc

    work page 2009

  4. [4]

    and Vassilvitskii, S

    Arthur, D. and Vassilvitskii, S. (2006a). How slow is the k-means method? In SCG '06: Proceedings of the twenty-second annual symposium on computational geometry . ACM Press

    work page 2006

  5. [5]

    and Vassilvitskii, S

    Arthur, D. and Vassilvitskii, S. (2006b). Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method. In Symposium on Foundations of Computer Science

    work page 2006

  6. [6]

    and Vassilvitskii, S

    Arthur, D. and Vassilvitskii, S. (2007). k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '07, page 1027–1035, USA. Society for Industrial and Applied Mathematics

    work page 2007

  7. [7]

    Awasthi, P., Charikar, M., Krishnaswamy, R., and Sinop, A. K. (2015). The Hardness of Approximation of Euclidean k-Means . In Arge, L. and Pach, J., editors, 31st International Symposium on Computational Geometry (SoCG 2015) , volume 34 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 754--767, Dagstuhl, Germany. Schloss Dagstuhl -- Le...

    work page 2015

  8. [8]

    Bachem, O., Lucic, M., Hassani, H., and Krause, A. (2016a). Fast and provably good seedings for k-means. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems , volume 29. Curran Associates, Inc

    work page 2016

Show all 47 references
  1. [9]

    H., and Krause, A

    Bachem, O., Lucic, M., Hassani, S. H., and Krause, A. (2016b). Approximate k-means++ in sublinear time. Proceedings of the AAAI Conference on Artificial Intelligence , 30(1)

    2016

  2. [10]

    Bachem, O., Lucic, M., and Krause, A. (2017a). Distributed and provably good seedings for k-means in constant rounds. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning , volume 70 of Proceedings of Machine Learning Rese...

    2017

  3. [11]

    Bachem, O., Lucic, M., and Krause, A. (2017b). Practical coreset constructions for machine learning. arXiv preprint arXiv:1703.06476

    2017 arXiv

  4. [12]

    Bahmani, B., Moseley, B., Vattani, A., Kumar, R., and Vassilvitskii, S. (2012). Scalable k-means++. Proc. VLDB Endow. , 5(7):622–633

    2012

  5. [13]

    Bhattacharya, A., Eube, J., R\" o glin, H., and Schmidt, M. (2020). Noisy, Greedy and Not so Greedy k-Means++ . In Grandoni, F., Herman, G., and Sanders, P., editors, 28th Annual European Symposium on Algorithms (ESA 2020) , volume 173 of Leibniz International Proceedings in I...

    2020

  6. [14]

    Blackard, J. (1998). Covertype [dataset]. UCI Machine Learning Repository

    1998

  7. [15]

    and Joachims, T

    Caruana, R. and Joachims, T. (2004). Kdd cup 2004: Protein homology dataset. https://kdd.org/kdd-cup/view/kdd-cup-2004/Data. Accessed: 2025-01-29

    2004

  8. [16]

    and Oppacher, F

    Cattral, R. and Oppacher, F. (2002). Poker hand [dataset]. UCI Machine Learning Repository

    2002

  9. [17]

    Charikar, M., Henzinger, M., Hu, L., V\" o tsch, M., and Waingarten, E. (2023). Simple, scalable and effective clustering via one-dimensional projections. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S., editors, Advances in Neural Information Proc...

    2023

  10. [18]

    Choo, D., Grunau, C., Portmann, J., and Rozhon, V. (2020). k-means++: few more steps yield constant approximation. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference on Machine Learning , volume 119 of Proceedings of Machine Learning Researc...

    2020

  11. [19]

    Cohen-Addad, V. (2018). A fast approximation scheme for low-dimensional k-means. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '18, page 430–440, USA. Society for Industrial and Applied Mathematics

    2018

  12. [20]

    and C.S., K

    Cohen-Addad, V. and C.S., K. (2019). Inapproximability of clustering in lp metrics. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 519--539

    2019

  13. [21]

    Cohen-Addad, V., Esfandiari, H., Mirrokni, V., and Narayanan, S. (2022). Improved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2022, page 1621–1628, Ne...

    2022

  14. [22]

    N., and Mathieu, C

    Cohen-Addad, V., Klein, P. N., and Mathieu, C. (2019). Local search yields approximation schemes for \ k\ -means and \ k\ -median in euclidean and minor-free metrics. SIAM Journal on Computing , 48(2):644--667

    2019

  15. [23]

    Cohen-Addad, V., Lattanzi, S., Norouzi-Fard, A., Sohler, C., and Svensson, O. (2020). Fast and accurate k-means++ via rejection sampling. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems , volume 3...

    2020

  16. [24]

    Dasgupta, S. (2003). How fast is k-means? In Sch \"o lkopf, B. and Warmuth, M. K., editors, COLT , volume 2777 of Lecture Notes in Computer Science , page 735. Springer

    2003

  17. [25]

    Dasgupta, S. (2008). The hardness of k-means clustering. Technical report, UC San Diego: Department of Computer Science & Engineering

    2008

  18. [26]

    Dasgupta, S. (2013). CSE 291 : Geometric Algorithms, Lecture 3 - Algorithms for k-means clustering

    2013

  19. [27]

    Feldman, D. (2020). Introduction to core-sets: an updated survey. arXiv preprint arXiv:2011.09384

    2020 arXiv

  20. [28]

    Friggstad, Z., Rezapour, M., and Salavatipour, M. R. (2019). Local search yields a ptas for \ k\ -means in doubling metrics. SIAM Journal on Computing , 48(2):452--480

    2019

  21. [29]

    A., and Rozho n , V

    Grunau, C., \" O z\" u do g ru, A. A., and Rozho n , V. (2023). Noisy k-Means++ Revisited . In G rtz, I. L., Farach-Colton, M., Puglisi, S. J., and Herman, G., editors, 31st Annual European Symposium on Algorithms (ESA 2023) , volume 274 of Leibniz International Proceedings in...

    2023

  22. [30]

    and Sadri, B

    Har-Peled, S. and Sadri, B. (2005). How fast is the k-means method? In SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms , pages 877--885, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics

    2005

  23. [31]

    Hastings, W. K. (1970). Monte carlo sampling methods using markov chains and their applications. Biometrika , 57(1):97--109

    1970

  24. [32]

    and Vazirani, V

    Jain, K. and Vazirani, V. V. (2001). Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM , 48(2):274–296

    2001

  25. [33]

    Jaiswal, R., Kumar, A., and Sen, S. (2014). A simple D2 -sampling based PTAS for k-means and other clustering problems. Algorithmica , 70(1):22--46

    2014

  26. [34]

    Jaiswal, R., Kumar, M., and Yadav, P. (2015). Improved analysis of D2 -sampling based PTAS for k-means and other clustering problems. Information Processing Letters , 115(2):100--103

    2015

  27. [35]

    and Shah, P

    Jaiswal, R. and Shah, P. (2024). Quantum (inspired) d^2 -sampling with applications

    2024

  28. [36]

    Johnson, W. B. and Lindenstrauss, J. (1984). Extensions of lipschitz maps into a hilbert space. Contemporary Mathematics , 26:189--206

    1984

  29. [37]

    M., Netanyahu, N

    Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., and Wu, A. Y. (2002). A local search approximation algorithm for k-means clustering. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry , SCG '02, page 10–18, New York, NY, USA....

    2002

  30. [38]

    Kelly, M., Longjohn, R., and Nottingham, K. (2021). Cdc diabetes health indicators dataset. The UCI Machine Learning Repository

    2021

  31. [39]

    Krishnapuram, B. (2008). Kdd cup 2008: Breast cancer dataset. https://kdd.org/kdd-cup/view/kdd-cup-2008/Data. Accessed: 2025-01-29

    2008

  32. [40]

    Kumar, A., Sabharwal, Y., and Sen, S. (2010). Linear-time approximation schemes for clustering problems in any dimensions. J. ACM , 57(2)

    2010

  33. [41]

    and Sohler, C

    Lattanzi, S. and Sohler, C. (2019). A better k-means++ algorithm via local search. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 3662--3671. PMLR

    2019

  34. [42]

    Lee, E., Schmidt, M., and Wright, J. (2017). Improved and simplified inapproximability for k-means. Inf. Process. Lett. , 120:40--43

    2017

  35. [43]

    Lloyd, S. (1982). Least squares quantization in pcm. IEEE Transactions on Information Theory , 28(2):129--137

    1982

  36. [44]

    Mahajan, M., Nimbhorkar, P., and Varadarajan, K. (2009). The planar k-means problem is np-hard. In Proceedings of the 3rd International Workshop on Algorithms and Computation , WALCOM '09, page 274–285, Berlin, Heidelberg. Springer-Verlag

    2009

  37. [45]

    Pollard, D. (1981). Strong consistency of k-means clustering. The Annals of Statistics , 9(1):135--140

    1981

  38. [46]

    Tang, E. (2019). A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , STOC 2019, page 217–228, New York, NY, USA. Association for Computing Machinery

    2019

  39. [47]

    R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G

    Wu, X., Kumar, V., Quinlan, J. R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G. J., Ng, A., Liu, B., Yu, P. S., Zhou, Z.-H., Steinbach, M., Hand, D. J., and Steinberg, D. (2008). Top 10 algorithms in data mining. Knowledge and Information Systems , 14(1):1--37

    2008

Pith tools

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