Pith. sign in

REVIEW 3 major objections 5 minor 43 references

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper establishes an $O(1)$-approximation algorithm for $k$-means in $\mathbb{R}^d$ that runs in $O(\log\log n \cdot \log\log\log n)$ MPC rounds with per-machine memory $n^\sigma$ and global memory $n^{1+\varepsilon}$—the first…

desk verdict Promising approach, but the main theorem doesn't follow: Lemma 4.2's key inequality fails with the stated constants, and Lemma 5.4's diameter-2 spanner cannot have n^{1+ε} edges for small ε. read the letter →

arxiv 2507.14089 v1 pith:4M6M7IXD submitted 2025-07-18 cs.DS

Vincent Cohen-Addad , Fabian Kuhn , Zahra Parsaeian This is my paper · ORCID
classification cs.DS MSC 68W2568W1568W2068Q25
keywords k-meansclusteringmassivelyparallelcomputationMPCmodelfacilitylocationLagrangianMultiplierPreservingprimal-dualalgorithmlocality-sensitivehashingrulingsets
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

The paper sets out to prove that the k-means clustering problem, in the massively parallel computation (MPC) model, can be approximated within a constant factor using only slightly more than linear total memory and arbitrarily small per-machine memory, while running in $O(\log\log n \cdot \log\log\log n)$ rounds. The main theorem states that for any constants $\sigma,\varepsilon>0$ and any $k,d\ge 1$, an $O(1)$-approximate solution on $n$ points in $\mathbb{R}^d$ can be computed with $O(n^\sigma)$ bits per machine and $O(n^{1+\varepsilon})$ bits globally. This is the first constant-factor approximation for the general k-means problem with exactly $k$ centers in $o(\log n)$ MPC rounds. The route is a constant-factor approximation for facility location that satisfies the Lagrangian-Multiplier-Preserving (LMP) property, so the classic reduction from k-means to facility location can be applied without losing the approximation guarantee.

What carries the argument

The load-bearing object is a Lagrangian-Multiplier-Preserving (LMP) constant-factor approximation for facility location: a primal-dual solution $(F',\alpha)$ satisfying $\sum_c \operatorname{cost}(c,F'(c)) \le \Lambda(\sum_c \alpha_c - |F'|\lambda)$. This property is what lets two facility-location solutions at opening costs $\lambda_1 \approx \lambda_2$ be combined into an exactly-$k$-center k-means solution with only constant-factor loss. Around that core sit a sparse locality-sensitive-hashing-based spanner that approximates every Euclidean distance by a one- or two-hop path in $O(n^{1+\varepsilon})$ edges; a parallel primal-dual routine that estimates facility radii and client dual values from approximate ball-size counts; and a two-stage ruling-set computation—an adapted randomized independent-set step followed by the fastest known low-memory $(2,O(\log\log\log n))$-ruling set algorithm—that selects well-separated cluster centers among the approximately-paid facilities.

What would settle it

Construct the graph of Lemma 5.4 on $n$ points equally spaced on a line and check whether every pair at Euclidean distance $D$ has a one- or two-hop path of total weight at most $D$ while the graph has at most $n^{1+\varepsilon}$ edges; a single pair whose two-hop graph distance exceeds its Euclidean distance by more than a constant would refute the lemma and with it the sublinear-memory implementation.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is that the MPC complexity of general Euclidean k-means drops below logarithmic rounds while keeping the exact-$k$ formulation. The algorithm's facility-location core is a parallel primal-dual routine: each facility gets an approximate radius $r_f$ at which it would be exactly paid for, each client gets an approximate dual value $\alpha_c = \min_f \max\{r_f^2,\operatorname{cost}(c,f)\}$, problematic clients are frozen, and the approximately-paid facilities are organized into a dependency graph. A two-stage ruling-set computation selects cluster centers so that all but a $1/\log n$ fraction of client dual weight is within constant distance, and one facility per cluster is opened. Because the facility-location solution satisfies the LMP property, the standard interpolation between two opening costs $\lambda_1,\lambda_2$ yields exactly $k$ centers with constant-factor expected cost, and $O(\log n)$ independent repetitions make the guarantee hold with high probability.

Load-bearing premise

The entire sublinear-memory implementation depends on the existence of a graph with $O(n^{1+\varepsilon})$ edges, produced by locality-sensitive hashing, in which every Euclidean distance is represented up to a constant factor by a one- or two-hop path; if that graph actually requires more edges than claimed, the per-machine memory guarantee cannot be met.

Editorial extensions

If this is right

  • General k-means can be approximated within a constant factor without relaxing the number of centers to $(1+\varepsilon)k$, using $O(n^{1+\varepsilon})$ total memory and $O(n^\sigma)$ per machine.
  • The round bound $O(\log\log n \cdot \log\log\log n)$ applies for every $k$ and $d$ after standard dimension-reduction and distance-scaling preprocessing.
  • Because the facility-location subroutine is LMP, any future improvement in its approximation constant transfers automatically to k-means through the same interpolation step.
  • Running $O(\log n)$ independent trials and keeping the approximately best solution turns the in-expectation guarantee into a high-probability constant-factor guarantee.
  • The per-machine memory exponent $\sigma$ can be chosen arbitrarily small, so the algorithm meets the fully-scalable requirement of the MPC model.

Reading between the lines

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

  • If the spanner lemma holds as stated, the same LMP facility-location core should carry over to other objectives reducible to facility location, such as k-median, because the reduction rests only on the relaxed triangle inequality used in Eq. (2).
  • The round count is set almost entirely by the ruling-set primitive; a constant-round $(O(1),O(1))$-ruling set in the low-memory MPC model—currently unknown—would immediately compress this algorithm to $O(\log\log n)$ or fewer rounds.
  • In practice the memory claims depend on the constants hidden in the LSH spanner; on high-dimensional data an implementation would need to verify that $O(n^\sigma)$ per machine is actually reachable with standard hash parameters and edge counts.
  • The LMP property is the part most likely to be reused: a facility-location solver that does not preserve dual multipliers cannot be plugged into this k-means reduction, so the contribution is a new kind of parallel solver, not just a faster implementation of an existing one.
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

3 major / 5 minor

Summary. The paper claims an MPC algorithm that computes an O(1)-approximation to the k-means problem in R^d in O(log log n · log log log n) rounds, using O(n^σ) bits of memory per machine and O(n^{1+ε}) bits of global memory for arbitrary constants σ, ε > 0. The approach follows the Jain–Vazirani primal-dual framework: it first develops a constant-factor LMP approximation for facility location (Algorithm 1), then applies the standard reduction from k-means to facility location, and finally implements both stages in the sublinear-memory MPC model using an LSH-based sparse graph and ruling-set algorithms. The main theorem is stated as the first constant-factor approximation for general k-means with exactly k centers in o(log n) MPC rounds.

Significance. If the main theorem were proven, it would be a substantial advance: prior work achieved constant-factor bicriteria approximations in O(1) rounds, but the present paper targets the exact-k version with a sublogarithmic round count. The paper is clearly organized, separates the high-level algorithm from the MPC implementation, and makes concrete use of known LSH and ruling-set subroutines. However, the proof contains load-bearing gaps that must be repaired before the result is established.

major comments (3)
  1. [§4.2, Lemma 4.2] The proof of Lemma 4.2 uses the inequality "CA ≥ Q·C_D^+" to conclude that a facility is paid, but Eq. (14) sets C_A = 8Γ^8, Q = 8Γ^4, and C_D^+ = 8Γ^4, so Q·C_D^+ = 64Γ^8, which is eight times larger than C_A. The chain of inequalities in Case 1 therefore does not imply the claimed lower bound, and Lemma 4.2—which is used in Step VI to define the facility f_c and in Lemma 4.6 to bound connection costs—is not established. This is a central error, and because the constants in Eq. (14) are interdependent across Lemmas 4.3–4.5, it is not a simple typo.
  2. [§5.1, Lemmas 5.2 and 5.4] The edge bound in Lemma 5.2 misses a factor of n. For each of the t = 5 ln n / p1 hash functions, the construction may add up to n−1 edges (when all points collide in one bucket), so the correct bound is |E_D| ≤ 5 n ln n / p1. This propagates to Lemma 5.4, where the union over O(log n) scales has up to 5 n log^2 n / p1 edges; with this corrected count, the choice s = (1+ε)/ε does not yield the claimed n^{1+ε} edge bound. Since Lemma 5.4 supplies the sparse graph on which the MPC implementation and the global-memory budget depend, the proof of the main theorem is not supported as written.
  3. [§4.1–4.2, Steps I–II vs. Lemmas 4.2–4.5] The high-level analysis in Section 4.2 reasons with exact radii r_f and exact values α*_c, whereas Algorithm 1 Step I computes approximate radii r̂_f and Step II computes α_c,0 from approximate graph neighborhoods. The lemmas do not explicitly show that their claims—such as α*_c ≤ max{r_f^2, cost(c,f)} in Lemma 4.3 or the no-facility-paid condition in Lemma 4.5—remain valid when the quantities are replaced by the approximations produced by the implemented Steps I and II. This gap between the analyzed algorithm and the implemented algorithm should be closed.
minor comments (5)
  1. [§4.4, Theorem 4.10] The theorem statement gives an approximation factor of (2 + 4δ^2)·Λ, but the proof concludes with (1 + 2(δ+1)^2)·(λ1/λ2)·Λ ≤ (2 + 4(δ+1)^2)·Λ; the theorem statement should match the proof.
  2. [§5.1, Lemma 5.2 proof] The probability bound contains a reversed inequality: the probability that x and y are not connected is (1−p1)^t, which is at most e^{−p1 t}, whereas the text writes that this probability is at least 1−e^{−p1 t}.
  3. [§5.2, Lemma 5.9] The lemma statement says the round complexity is O(t log log n), but the proof gives O(t log log log n + log log n · log log log n); the statement should be adjusted to the actual bound.
  4. [§5.1, Lemma 5.4] A purported lower bound of Ω(n^{3/2}) for any diameter-2 graph is not valid; a star graph has diameter 2 and only O(n) edges. The real issue with Lemma 5.4 is the missing factor of n in the edge count, not an impossibility of the claimed graph.
  5. [§5.3, Lemma 5.13 proof] The proof states "we choose C_A = Γ^4·Q", which conflicts with the fixed value C_A = 8Γ^8 in Eq. (14); this should be clarified or the constants should be made consistent.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the k-means guarantee follows from a self-contained LMP facility location analysis, with self-citations used only as subroutines.

full rationale

The central derivation is not circular. The paper proves a constant-factor LMP facility location approximation in Section 4 (Lemmas 4.2–4.6 and Theorem 4.7) and then applies the Jain–Vazirani Lagrangian interpolation to convert it into a constant-factor k-means approximation (Theorem 4.10). The facility location analysis is self-contained: it does not assume the k-means result, and its constants are chosen as explicit functions of a single spanner-approximation parameter rather than fitted to any target output. Self-citations such as CAGLS23, CMZ22, CLN21, BGKO23, and GP24 appear as imports of standard subroutines (LSH hash evaluation, ruling-set algorithms, LMP background) or as related-work context, and the main theorems do not reduce to those citations. In particular, the LSH-based graph approximation in Lemma 5.4 is stated and proved locally from the LSH family of Lemma 5.3, and the ruling-set machinery is applied to an explicitly constructed graph rather than used to define the approximation ratio. Any concern about the claimed edge bound in Lemma 5.4 is a correctness or verification issue, not a circularity: nothing in the derivation is equivalent, by construction, to its own inputs, and no fitted parameter is renamed as a prediction. The paper therefore receives a low circularity score.

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

The paper introduces no data-fitted free parameters and no new physical or mathematical entities. The many constants in Eq. (14) are explicit functions of Gamma and are chosen analytically for the proof, not fitted to any data. The assumptions listed are the cited black-box algorithmic tools and structural preconditions on which the MPC implementation rests.

assumptions (6)
  • domain assumption The LSH family from Lemma 5.3 exists with the stated sensitivity parameters and can be evaluated in O(1) MPC rounds with n^{1+o(1)}d total space.
    Invoked in Lemma 5.4 to build the sparse graph G and cited to AI06 and CMZ22; not proved in this paper.
  • domain assumption The MPC sorting and aggregation routine of GSZ11 and the approximate sum-via-minimum technique of MS08 can be implemented in O(1) rounds with the stated memory.
    Used in Lemmas 5.5, 5.6, 5.10 and throughout the implementation.
  • domain assumption The low-memory MPC ruling set algorithm of KPP20 computes a (2, O(log log log n))-ruling set in O(log log n log log log n) rounds, and the MIS algorithm of GU19 runs in the claimed time.
    Used as a black box in Lemmas 5.7 and 5.9 to select cluster centers.
  • domain assumption Random projection and scaling reductions preserve k-means cost up to (1 +/- epsilon) and allow d = O(log k) and distances in [1, poly(n)].
    Invoked in Section 2, Eq. (1), citing BBCA19 and ANFSW20; the algorithm is only stated for the reduced instance.
  • standard math The relaxed triangle inequality (2) for squared Euclidean distances.
    Used in Lemma 4.2 and elsewhere; follows from Cauchy-Schwarz and the paper states it as a known property.
  • ad hoc to paper The number of facilities opened by the algorithm is monotonically non-increasing in the opening cost lambda.
    Assumed in Lemma 5.18 to justify the discretized search over lambda; no proof is given and the algorithm is randomized and approximate, so monotonicity is not self-evident.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem." pith.science (2026). https://pith.science/paper/4M6M7IXD

@misc{pith2026250714089,
  author       = {Pith},
  title        = {Pith review of: An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4M6M7IXD}},
  note         = {Machine review of arXiv:2507.14089}
}
abstract

In this paper, we present an efficient massively parallel approximation algorithm for the $k$-means problem. Specifically, we provide an MPC algorithm that computes a constant-factor approximation to an arbitrary $k$-means instance in $O(\log\log n \cdot \log\log\log n)$ rounds. The algorithm uses $O(n^\sigma)$ bits of memory per machine, where $\sigma > 0$ is a constant that can be made arbitrarily small. The global memory usage is $O(n^{1+\varepsilon})$ bits for an arbitrarily small constant $\varepsilon > 0$, and is thus only slightly superlinear. Recently, Czumaj, Gao, Jiang, Krauthgamer, and Vesel\'{y} showed that a constant-factor bicriteria approximation can be computed in $O(1)$ rounds in the MPC model. However, our algorithm is the first constant-factor approximation for the general $k$-means problem that runs in $o(\log n)$ rounds in the MPC model. Our approach builds upon the foundational framework of Jain and Vazirani. The core component of our algorithm is a constant-factor approximation for the related facility location problem. While such an approximation was already achieved in constant time in the work of Czumaj et al.\ mentioned above, our version additionally satisfies the so-called Lagrangian Multiplier Preserving (LMP) property. This property enables the transformation of a facility location approximation into a comparably good $k$-means approximation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

  1. [1]

    N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms , 7(4):567--583, 1986

    work page 1986

  2. [2]

    Awerbuch, A

    B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proc.\ 30th IEEE Symp. on Foundations of Computer Science (FOCS) , pages 364--369, 1989

    work page 1989

  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 Proc.\ 47th IEEE Symp.\ on Foundations of Computer Science (FOCS) , pages 459--468, 2006

    work page 2006

  4. [4]

    Streaming k-means approximation

    Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. Streaming k-means approximation. In Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta, editors, Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 Decembe...

    work page 2009

  5. [5]

    Better guarantees for \ k\ -means and euclidean \ k\ -median by primal-dual algorithms

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

    work page 2020

  6. [6]

    Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma

    Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma. In Proc.\ 51st ACM Symp.\ on Theory of Computing (STOC) , page 1039–1050, 2019

    work page 2019

  7. [7]

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

    Maria Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general topologies. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2013, December 5-10, 2013, Lake Tahoe, Nevada, United States , pages 1995--2003, 2013

    work page 2013

  8. [8]

    Node and edge averaged complexities of local graph problems

    Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. Node and edge averaged complexities of local graph problems. Distributed Computing , 36(4):451--473, 2023

    work page 2023

Show all 43 references
  1. [9]

    Blelloch, Anupam Gupta, and Kanat Tangwongsan

    Guy E. Blelloch, Anupam Gupta, and Kanat Tangwongsan. Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design. In Guy E. Blelloch and Maurice Herlihy, editors, 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '12, Pittsburgh, PA,...

    2012

  2. [10]

    Efficient k-anonymization using clustering techniques

    Ji-Won Byun, Ashish Kamra, Elisa Bertino, and Ninghui Li. Efficient k-anonymization using clustering techniques. In International conference on database systems for advanced applications , pages 188--200. Springer, 2007

    2007

  3. [11]

    Scalable k-means clustering via lightweight coresets

    Olivier Bachem, Mario Lucic, and Andreas Krause. Scalable k-means clustering via lightweight coresets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD) , pages 1119--1127. ACM, 2018

    2018

  4. [12]

    Blelloch and Kanat Tangwongsan

    Guy E. Blelloch and Kanat Tangwongsan. Parallel approximation algorithms for facility-location problems. In Friedhelm Meyer auf der Heide and Cynthia A. Phillips, editors, SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, T...

    2010

  5. [13]

    Distributed clustering via LSH based data partitioning

    Aditya Bhaskara and Maheshakya Wijewardena. Distributed clustering via LSH based data partitioning. In Proceedings of the 35th International Conference on Machine Learning , pages 570--579, 2018

    2018

  6. [14]

    Breaching the 2 LMP approximation barrier for facility location with applications to k -median

    Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn. Breaching the 2 LMP approximation barrier for facility location with applications to k -median. In Proc.\ ACM-SIAM Symp.\ on Discrete Algorithms (SODA) , pages 940--986, 2023

    2023

  7. [15]

    Near-optimal private and scalable k -clustering

    Vincent Cohen - Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Near-optimal private and scalable k -clustering. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Syste...

    2022

  8. [16]

    Artur Czumaj, Guichen Gao, Mohsen Ghaffari, and Shaofeng H. - C. Jiang. Fully scalable MPC algorithms for euclidean k-center. In Proc.\ 52nd Int.\ Coll.\ on Automata, Languages, and Programming (ICALP) , volume 334 of LIPIcs , pages 64:1--64:20, 2025

    2025

  9. [17]

    Artur Czumaj, Guichen Gao, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Pavel Vesel \' y . Fully-scalable MPC algorithms for clustering in high dimension. In Proc.\ 51st Int.\ Coll.\ on Automata, Languages, and Programming (ICALP) , pages 50:1--50:20, 2024

    2024

  10. [18]

    Online k-means clustering

    Vincent Cohen - Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means clustering. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event , volume 13...

    2021

  11. [19]

    Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang

    Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. In 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 450--461. IEEE, 2022

    2022

  12. [20]

    Time and space optimal massively parallel algorithm for the 2-ruling set problem

    M \' e lanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and space optimal massively parallel algorithm for the 2-ruling set problem. In 37th Int.\ Symp.\ on Distributed Computing (DISC) , pages 11:1--11:12, 2023

    2023

  13. [21]

    Parallel and efficient hierarchical k-median clustering

    Vincent Cohen - Addad, Silvio Lattanzi, Ashkan Norouzi - Fard, Christian Sohler, and Ola Svensson. Parallel and efficient hierarchical k-median clustering. In Proc.\ Conf.\ on Advances in Neural Information Processing (NeurIPS) , pages 20333--20345, 2021

    2021

  14. [22]

    Mirrokni, and Peilin Zhong

    Vincent Cohen - Addad, Vahab S. Mirrokni, and Peilin Zhong. Massively parallel k-means clustering for perturbation resilient instances. In Proc.\ Int.\ Conf.\ on Machine Learning (ICML) , pages 4180--4201, 2022

    2022

  15. [23]

    Better streaming algorithms for clustering problems

    Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy. Better streaming algorithms for clustering problems. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA , pages ...

    2003

  16. [24]

    Mirrokni

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry , page 253–262, 2004

    2004

  17. [25]

    Fast clustering using mapreduce

    Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using mapreduce. In Chid Apt \' e , Joydeep Ghosh, and Padhraic Smyth, editors, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 20...

    2011

  18. [26]

    Ghaffari

    M. Ghaffari. An improved distributed algorithm for maximal independent set. In Proc.\ ACM-SIAM Symp.\ on Discrete Algorithms (SODA) , pages 270--277, 2016

    2016

  19. [27]

    Massively parallel ruling set made deterministic

    Jeff Giliberti and Zahra Parsaeian. Massively parallel ruling set made deterministic. In Dan Alistarh, editor, Proc.\ 38th Int.\ Symp.\ on Distributed Computing (DISC) , volume 319 of LIPIcs , pages 29:1--29:21, 2024

    2024

  20. [28]

    Goodrich, Nodari Sitchinava, and Qin Zhang

    Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the MapReduce framework. In Proc.\ Int.\ Symp.\ on Algorithms and Computation (ISAAC) , pages 374--383. Springer, 2011

    2011

  21. [29]

    Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation

    Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proc.\ 30th ACM-SIAM Symp.\ on Discrete Algorithms (SODA) , pages 1636--1653, 2019

    2019

  22. [30]

    Massively parallel computation: A lgorithms and applications

    Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, and Sergei Vassilvitskii. Massively parallel computation: A lgorithms and applications. Foundations and Trends in Optimization , 5(4):340--417, 2023

    2023

  23. [31]

    Nearest neighbors in high-dimensional spaces

    Piotr Indyk. Nearest neighbors in high-dimensional spaces. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition , pages 877--892. Chapman and Hall/CRC, 2004

    2004

  24. [32]

    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. J. ACM , 48(2):274--296, 2001

    2001

  25. [33]

    Deterministic distributed ruling sets of line graphs

    Fabian Kuhn, Yannic Maus, and Simon Weidner. Deterministic distributed ruling sets of line graphs. In Proc.\ 25th Int.\ Coll.\ on Structural Information and Communication Complexity (SIROCCO) , pages 193--208, 2018

    2018

  26. [34]

    Kothapalli and S

    K. Kothapalli and S. V. Pemmaraju. Super-fast 3-ruling sets. In FSTTCS , volume 18 of LIPIcs , pages 136--147, 2012

    2012

  27. [35]

    Pemmaraju

    Kishore Kothapalli, Shreyas Pai, and Sriram V. Pemmaraju. Sample-and-gather: Fast ruling set algorithms in the low-memory MPC model. In Proc.\ 40th IARCS Conf.\ on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , volume 182 of LIPIcs , pages 28:1-...

    2020

  28. [36]

    Karloff, Siddharth Suri, and Sergei Vassilvitskii

    Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce . In Proc.\ ACM-SIAM Symp. on Discrete Algorithms (SODA) , pages 938--948, 2010

    2010

  29. [37]

    Least squares quantization in pcm

    Stuart Lloyd. Least squares quantization in pcm. IEEE transactions on information theory , 28(2):129--137, 1982

    1982

  30. [38]

    M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing , 15:1036--1053, 1986

    1986

  31. [39]

    Quantizing for minimum distortion

    Joel Max. Quantizing for minimum distortion. IRE Transactions on Information Theory , 6(1):7--12, 1960

    1960

  32. [40]

    Online facility location

    Adam Meyerson. Online facility location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA , pages 426--431. IEEE Computer Society, 2001

    2001

  33. [41]

    Fast distributed algorithms for computing separable functions

    Damon Mosk - Aoyama and Devavrat Shah. Fast distributed algorithms for computing separable functions. IEEE Trans. Inf. Theory , 54(7):2997--3007, 2008

    2008

  34. [42]

    S. Pai, G. Pandurangan, S. V. Pemmaraju, T. Riaz, and P. Robinson. Symmetry breaking in the congest model: Time- and message-efficient algorithms for ruling sets. In Proc.\ Symp.\ on Distributed Computing (DISC) , volume 91 of LIPIcs , pages 38:1--38:16, 2017

    2017

  35. [43]

    Yang, and Peilin Zhong

    Zhao Song, Lin F. Yang, and Peilin Zhong. Sensitivity sampling over dynamic geometric data streams with applications to k-clustering. arXiv preprint arXiv:1802.00459 , 2018

    2018 arXiv

Pith tools

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