Pith. sign in

REVIEW 1 major objections 6 minor 49 references

Fully Scalable MPC Algorithms for Euclidean k-Center

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

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

Pith's one-line read This paper establishes the first constant-round fully scalable MPC algorithms for Euclidean k-center, achieving (2+ε)-approximation with exactly k centers in low dimension and O(log n/log log n)-approximation in high dimension.

desk verdict Genuine advance for fully-scalable MPC k-center in low dimension; the high-dimensional claim should be checked against its black-box dependence. read the letter →

arxiv 2504.16382 v2 pith:2E4B2YBF submitted 2025-04-23 cs.DS cs.DC

Artur Czumaj , Guichen Gao , Mohsen Ghaffari , Shaofeng H.-C. Jiang This is my paper · ORCID
classification cs.DScs.DC MSC 68W1568W2068U05
keywords k-centerMassivelyParallelComputationfullyscalablealgorithmrulingsetminimumdominatinggeometrichashingconsistentEuclideanclustering
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 claims the first constant-round fully scalable MPC algorithms for Euclidean $k$-center, in both the low- and the high-dimensional regime. In low dimension it achieves a $(2+\varepsilon)$-approximation using exactly $k$ centers, and a bi-criteria $(1+\varepsilon)$-approximation using $(1+\varepsilon)k$ centers, each in $O(\log_s n)$ rounds with local memory $(\Omega(d/\varepsilon))^{\Omega(d)} \operatorname{poly}\log n$ and total memory $O(n \operatorname{poly}\log n \cdot (O(d/\varepsilon))^{O(d)})$. In high dimension it gives the first fully scalable MPC algorithm, an $O(\varepsilon^{-1} \log n/\log\log n)$-approximation, with $\operatorname{poly}(d\log n)$ local memory and $n^{1+\varepsilon} \operatorname{poly}(d\log n)$ total memory. These results improve on earlier fully scalable algorithms that needed super-constant rounds, returned $k(1+o(1))$ centers, and worked only for constant dimension.

What carries the argument

The load-bearing object is a geometric hash function $f:\mathbb{R}^d\to\mathbb{R}^d$ (Lemma 3.1) with three properties: each bucket has diameter $\ell=O(d^{1.5}\beta)$; the buckets can be partitioned into $d+1$ groups whose distinct buckets are at $\ell_\infty$-distance greater than $\beta$; and the union of all bucket $\tau$-annuli avoids the periodic grid complement $L(z,2b)^d$. This hash turns the whole space into small, locally decoupled cells; any set of $\ell_\infty$-diameter at most $\beta$ meets at most $d+1$ buckets, so in low dimension every MIS or MDS decision depends on at most $(d/\varepsilon)^{O(d)}$ points that fit on a single machine. In high dimension the machinery is a $(\Gamma,\Lambda)$-consistent hash (Lemma 3.4), a hash under which any small-diameter set intersects few buckets, with $\Lambda=\operatorname{poly}(\log n)$; after preprocessing, one-round Luby's is analyzed by an assignment sequence whose extension probabilities multiply to an $O(\log n/\log\log n)$ domination bound.

What would settle it

Try to implement Lemma 6.8 with the exact ball $A=B(p,\tau)$ on a dataset in $d=O(\log n)$ whose $\tau$-balls have large overlap; if the min-label query requires local memory $\omega(\operatorname{poly}(d\log n))$ or total memory $n^{1+\omega(\varepsilon)}$, the high-dimensional guarantee collapses. Separately, for low dimension, compute the hash buckets of Lemma 3.1 for $d=2$, $\beta=\tau=1$, and check whether any point of any bucket's $\tau$-annulus lies in $L(z,2b)^2$; a single such point falsifies Lemma 3.1.

Watch

Extended reading notes

Core claim

The paper's central claim is that Euclidean $k$-center can be solved by fully scalable MPC algorithms through geometric ruling sets and minimum dominating sets, with the Euclidean structure supplied by hashing. A $\tau$-independent set of size at most $k$ is a valid center set once $\tau\ge 2\,OPT$, so a $(2\tau,\gamma\tau)$-ruling set yields a $\gamma$-approximation; symmetrically, a $(1+\varepsilon)$-approximate $\tau$-minimum dominating set yields a $(1+\varepsilon,1+\varepsilon)$ bi-criteria solution. In low dimension a new geometric hash splits $\mathbb{R}^d$ into buckets of diameter $O(d^{1.5}\tau)$ organized into $d+1$ groups that are $\tau$-separated inside each group; each bucket's maximal independent set or dominating set can then be computed on one machine, because only $(d/\varepsilon)^{O(d)}$ nearby points are relevant. In high dimension, consistent hashing preprocesses the point set so that every $\tau$-ball among representatives has size $\operatorname{poly}(\log n)$, and a one-round Luby-style algorithm with a random assignment sequence provably dominates every point within $O(\varepsilon^{-1}\log n/\log\log n)\tau$ steps, improving on the $\Theta(\log n)$ that one-round Luby's achieves on general graphs.

Load-bearing premise

The high-dimensional theorem treats Lemma 6.8 as a black box: an MPC routine that, for every point $p$, returns the minimum random label inside an approximate ball $A$ with $B(p,\tau)\subseteq A\subseteq B(p,O(\varepsilon^{-1})\tau)$ in $O(\log_s n)$ rounds using $\operatorname{poly}(d\log n)$ local and $n^{1+\varepsilon}\operatorname{poly}(d\log n)$ total memory. If that primitive cannot be built with these guarantees, the $O(\log n/\log\log n)$ claim fails.

Editorial extensions

If this is right

  • For local memory $s=n^\sigma$ with constant $\sigma\in(0,1)$, the low-dimensional algorithms run in a constant number of rounds, matching the round complexity of summing $n$ numbers.
  • The $(2+\varepsilon)$ ratio with exactly $k$ centers is essentially the best possible, since $2$-approximation is the sequential optimum for $k$-center.
  • The $(1+\varepsilon,1+\varepsilon)$ bi-criteria algorithm returns $(1+\varepsilon)k$ centers, almost matching the information-theoretic minimum of $k$ centers, and is the first such fully scalable guarantee.
  • For $d=o(\log n/\log\log n)$, the algorithms use $s\ge n^\delta$ local memory and $n^{1+o(1)}$ total memory, improving the previously studied parameter regime in both approximation ratio and round count.
  • In high dimension the $O(\varepsilon^{-1}\log n/\log\log n)$ ratio beats the $\Omega(\log n)$ distortion lower bound that tree-embedding approaches to high-dimensional clustering would face.

Reading between the lines

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

  • The $d+1$-group hash is a generic local-decoupling device; a natural extension is to use it for other Euclidean bottleneck problems solvable by greedy local elimination, since only its first two properties are used for MIS while the third serves MDS.
  • The high-dimensional analysis suggests a transferable statement: one-round Luby's on any point set with $\operatorname{poly}(\log n)$-bounded $\tau$-neighborhoods gives $O(\log n/\log\log n)$-ruling sets, whereas on general graphs it is $\Theta(\log n)$; the improvement comes from bounded neighborhoods, not from the Euclidean metric itself.
  • For the MDS algorithm, replacing the exhaustive enumeration of $(d/\varepsilon)^{O(d)}$ hash shifts by a random shift could reduce total memory at the cost of a probabilistic guarantee; the paper does not explore this trade-off.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 6 minor

Summary. The paper designs fully scalable MPC algorithms for Euclidean k-center. In low dimension, it gives a (2+ε)-approximation using exactly k centers and a (1+ε,1+ε)-bi-criteria algorithm, both in O(log_s n) rounds, with local memory (Ω(dε^{-1}))^{Ω(d)} poly log n and total memory O(n poly log n (O(dε^{-1}))^{O(d)}). In high dimension, it gives an O(ε^{-1} log n/log log n)-approximation in O(log_s n) rounds with poly(d log n) local memory and O(n^{1+ε} poly(d log n)) total memory. The algorithms are obtained via reductions to geometric ruling-set and minimum-dominating-set problems; the low-dimensional results rely on a new geometric hashing construction (Lemma 3.1), while the high-dimensional result uses a preprocessing step based on consistent hashing followed by a one-round Luby-type procedure.

Significance. If correct, these are the first constant-round fully scalable MPC algorithms for Euclidean k-center with a (2+ε) approximation in low dimension, and the first fully scalable algorithm in high dimension, improving substantially over the previous super-constant-round, super-constant-approximation results. The low-dimensional proofs are essentially self-contained and the new geometric hashing lemma (Lemma 3.1), with its third property on τ-annuli, is a nontrivial technical contribution. The high-dimensional result is an interesting extension of one-round Luby's algorithm and the ruling-set analysis is a substantive new argument; however, it rests on a black-box approximate-ball MPC primitive restated from [CGJ+24].

major comments (1)
  1. [Section 6, Lemma 6.8 (and Theorem 1.3)] The high-dimensional result Theorem 1.3 depends entirely on Lemma 6.8, restated as [CGJ+24, Theorem 3.1], but the manuscript gives no proof, proof sketch, or parameter-by-parameter derivation of this primitive. The claim is load-bearing: the ruling-set analysis in Fact 6.4 and Lemma 6.6 requires the approximate ball to satisfy A_P(p,τ) ⊆ B(p,O(ε^{-1})τ), the procedure to be deterministic, and the total memory to be O(n^{1+ε} poly(d log n)). If the actual theorem in [CGJ+24] provides only a ball with an extra log n factor in the radius, or a randomized procedure, or a larger memory bound, then the claimed O(ε^{-1} log n/log log n) approximation ratio does not follow. I recommend that the authors add an appendix proving Lemma 6.8 or at least deriving it from the cited theorem with all constants and resource bounds checked; as written, the high-dimensional contribution is not self-contained and cannot be fully verified from the manuscript alone.
minor comments (6)
  1. [Section 6.1, Lemma 6.9] In the definition of Eext, the phrase "x'_m passes the test in line 2" appears to invert the stopping condition: the subsequent proof treats Eext as the event that the sequence extends, which requires x'_m not to be added by Algorithm 5; please correct the wording.
  2. [Section 5, equation (2)] The displayed equality "= |M^*| + Σ ..." should be "≤", since the sum over u∈f_v(P) of |M^*∩f^{-1}(u)| is at most |M^*|, not equal to it.
  3. [Section 5, after equation (5)] The sentence "it can be observed that \hat L(0) = L(z,2b)" is inconsistent with the definitions: \hat L(0) is a union of length-4b boundary intervals, whereas L(z,2b) is the complementary middle intervals; the intended statement is that \hat L(0) equals the complement of L(z,2b).
  4. [Section 3, Lemma 3.1 and Section 5] The notation "L(z,2b)^d" is used both for the d-th Cartesian power and for its complement; please introduce a separate symbol (e.g., an overline) to avoid ambiguity.
  5. [Section 7, Algorithm 7 line 5] Please clarify that the "(2τ,γτ)-ruling set" is obtained by invoking Lemmas 4.1 or 6.1 with threshold 2τ; the comment "γ=2(1+ε)" is correct only after this scaling.
  6. [Appendix B.1] The upper-bound proof for one-round Luby's algorithm is presented as a sketch; since this is a secondary observation not used in the main theorems, either mark it explicitly as non-essential or expand it to a full proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's new claims are proved here or rest on cited theorems with stated guarantees; self-citations are not load-bearing reductions to the target.

full rationale

The derivation chain is not circular. Low-dimensional Theorems 1.1 and 1.2 rest on Lemmas 4.1 and 5.1, whose geometric core Lemma 3.1 is largely proved in Appendix A; the construction and the first two properties are imported from [CJK+22]/[CFJ+22], but the new third property is established in the appendix, and the subsequent MIS/MDS arguments (Lemmas 4.7, 4.8, Fact 5.2, the averaging over shifts) are self-contained. The high-dimensional Theorem 1.3 does import a same-author primitive, Lemma 6.8 from [CGJ+24, Thm 3.1], as a black box; this is a published, parameter-free MPC procedure with explicit sandwich and complexity guarantees, and the paper's own contribution is the consistent-hashing preprocessing plus the configuration/union-bound analysis of the auxiliary sequence (Lemmas 6.5, 6.6, 6.9, 6.12), which does not simply rename or fit the primitive's output. No fitted parameter is relabeled as a prediction, no target quantity appears in the assumptions of the cited theorems, and no 'uniqueness' theorem is invoked to force a choice. If Lemma 6.8's guarantees were mis-stated or inapplicable, Theorem 1.3 would be at correctness risk, but that is not circularity. Hence score 0.

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

No free parameters are fitted to data; ε, τ, and algorithm constants are analytic inputs. The hash parameters β, ℓ, Γ, Λ are set by the proofs. The main external axioms are the two black-box results from the authors' prior work (consistent hashing and the approximate-ball MPC primitive), plus standard tools. No new entities are postulated.

assumptions (5)
  • domain assumption The consistent hashing construction of [CJK+22, Theorem 5.1] (Lemma 3.4) exists with diameter bound ℓ and consistency Λ = exp(8d/Γ)·O(d log d), describable in poly(d) space.
    Used in Algorithm 4 and Lemma 6.1 for the high-dimensional ruling set; adopted as a black box from prior published work.
  • domain assumption The deterministic MPC procedure of [CGJ+24, Theorem 3.1] (Lemma 6.8) computes min(h(A^β_P(p,τ))) for approximate balls satisfying B(p,τ)⊆A^β(p,τ)⊆B(p,O(ε^{-1})τ) within stated round and space bounds.
    Central to implementing Algorithm 5 in MPC for high dimension; cited from prior work of the same authors.
  • standard math Johnson-Lindenstrauss lemma (Lemma 6.7) preserves all pairwise distances up to (1±ε) factors when projecting to O(ε^{-2} log n) dimensions.
    Used to reduce dimension to O(log n) in the high-dimensional regime.
  • standard math Packing property (Lemma 2.1): a point set in R^d with mutual distance ≥ ρ and diameter D has size at most (3D/ρ)^d.
    Used to bound the number of grid points and bucket sizes throughout the low-dimension algorithms.
  • standard math Claim 6.10 from [CGJ+24] on the symmetry of independent uniform random labels under conditioning on a partial order.
    Used in the analysis of the one-round Luby's sequence, Lemma 6.9.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully Scalable MPC Algorithms for Euclidean k-Center." pith.science (2026). https://pith.science/paper/2E4B2YBF

@misc{pith2026250416382,
  author       = {Pith},
  title        = {Pith review of: Fully Scalable MPC Algorithms for Euclidean k-Center},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2E4B2YBF}},
  note         = {Machine review of arXiv:2504.16382}
}
abstract

The $k$-center problem is a fundamental optimization problem with numerous applications in machine learning, data analysis, data mining, and communication networks. The $k$-center problem has been extensively studied in the classical sequential setting for several decades, and more recently there have been some efforts in understanding the problem in parallel computing, on the Massively Parallel Computation (MPC) model. For now, we have a good understanding of $k$-center in the case where each local MPC machine has sufficient local memory to store some representatives from each cluster, that is, when one has $\Omega(k)$ local memory per machine. While this setting covers the case of small values of $k$, for a large number of clusters these algorithms require undesirably large local memory, making them poorly scalable. The case of large $k$ has been considered only recently for the fully scalable low-local-memory MPC model for the Euclidean instances of the $k$-center problem. However, the earlier works have been considering only the constant dimensional Euclidean space, required a super-constant number of rounds, and produced only $k(1+o(1))$ centers whose cost is a super-constant approximation of $k$-center. In this work, we significantly improve upon the earlier results for the $k$-center problem for the fully scalable low-local-memory MPC model. In the low dimensional Euclidean case in $\mathbb{R}^d$, we present the first constant-round fully scalable MPC algorithm for $(2+\varepsilon)$-approximation. We push the ratio further to $(1 + \varepsilon)$-approximation albeit using slightly more $(1 + \varepsilon)k$ centers. All these results naturally extends to slightly super-constant values of $d$. In the high-dimensional regime, we provide the first fully scalable MPC algorithm that in a constant number of rounds achieves an $O(\log n/ \log \log n)$-approximation for $k$-center.

Figures

Figures reproduced from arXiv: 2504.16382 by the authors.

Figure 1
Figure 1. A space partition in 2D with T = 3 and α = 5. The first group is squares with side-length 5τ /√ 2 (the blank space), the second is the red-shaded rectangles, and the third is the cross-like structures in blue shades. A key property of this decomposition is that the MIS computation in each region can be done independently within each group, as regions are τ -separated. This yields an O(T logs n)-round MPC algorithm: … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 22 canonical work pages

  1. [2]

    Massively parallel minimum spanning tree in general metric spaces

    Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Lacki, Vahab Mirrokni, and Peilin Zhong. Massively parallel minimum spanning tree in general metric spaces. In SODA , pages 143--174, 2025. https://doi.org/10.1137/1.9781611978322.5 doi:10.1137/1.9781611978322.5

    work page doi:10.1137/1.9781611978322.5 2025

  2. [3]

    A 2-Approximation Algorithm for Data-Distributed Metric k-Center

    Sepideh Aghamolaei and Mohammad Ghodsi. A 2-approximation algorithm for data-distributed metric k -center. arXiv preprint arXiv:2309.04327 , 2023. https://arxiv.org/abs/2309.04327 arXiv:2309.04327

    work page Pith review arXiv 2023

  3. [4]

    Network decomposition and locality in distributed computation

    Baruch Awerbuch, Andrew V Goldberg, Michael Luby, and Serge A Plotkin. Network decomposition and locality in distributed computation. In FOCS , pages 364--369, 1989. https://doi.org/10.1109/SFCS.1989.63504 doi:10.1109/SFCS.1989.63504

    arXiv 1989

  4. [5]

    $k$-Center Clustering with Outliers in the MPC and Streaming Model

    Mark de Berg, Leyla Biabani, and Morteza Monemizadeh. k -center clustering with outliers in the MPC and streaming model. In IPDPS , pages 853--863, 2023. https://arxiv.org/abs/2302.12811 arXiv:2302.12811

    work page Pith review arXiv 2023

  5. [6]

    Mirrokni

    MohammadHossein Bateni, Hossein Esfandiari, Manuela Fischer, and Vahab S. Mirrokni. Extreme k -center clustering. In AAAI , pages 3941--3949, 2021. https://doi.org/10.1609/AAAI.V35I5.16513 doi:10.1609/AAAI.V35I5.16513

    work page doi:10.1609/aaai.v35i5.16513 2021

  6. [7]

    Communication steps for parallel query processing

    Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. Journal of the ACM , 64(6):40:1--40:58, 2017. https://doi.org/10.1145/3125644 doi:10.1145/3125644

    doi:10.1145/3125644 2017

  7. [8]

    k -center clustering in distributed models

    Leyla Biabani and Ami Paz. k -center clustering in distributed models. In SIROCCO , pages 83--100, 2024. https://doi.org/10.1007/978-3-031-60603-8\_5 doi:10.1007/978-3-031-60603-8\_5

    doi:10.1007/978-3-031-60603-8 2024

  8. [9]

    Distributed clustering via LSH based data partitioning

    Aditya Bhaskara and Maheshakya Wijewardena. Distributed clustering via LSH based data partitioning. In ICML , pages 569--578, 2018. URL: http://proceedings.mlr.press/v80/bhaskara18a.html

    work page 2018

Show all 49 references
  1. [11]

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

    Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. arXiv preprint arXiv:2204.02095 , 2022. The latest version has additional results compared to the prelim...

    2022 arXiv

  2. [12]

    Artur Czumaj, Guichen Gao, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Pavel Vesel \' y . Fully-scalable MPC algorithms for clustering in high dimension. In ICALP , pages 50:1--50:20, 2024. https://doi.org/10.4230/LIPICS.ICALP.2024.50 doi:10.4230/LIPICS.ICALP.2024.50

    2024 doi

  3. [13]

    Artur Czumaj, Shaofeng H. - C. Jiang, Robert Krauthgamer, Pavel Vesel \' y , and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. In FOCS , pages 450--461, 2022. https://doi.org/10.1109/FOCS54457.2022.00050 doi:10.1109/FOCS54457.2022.00050

    2022

  4. [14]

    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 DISC , pages 11:1--11:12, 2023. https://doi.org/10.4230/LIPICS.DISC.2023.11 doi:10.4230/LIPICS.DISC.2023.11

    2023 doi

  5. [15]

    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 NeurIPS , pages 20333--20345, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/aa495e18c7e3a21a4e48923b92048...

    2021

  6. [16]

    Mirrokni, and Peilin Zhong

    Vincent Cohen - Addad, Vahab S. Mirrokni, and Peilin Zhong. Massively parallel k-means clustering for perturbation resilient instances. In ICML , pages 4180--4201, 2022. URL: https://proceedings.mlr.press/v162/cohen-addad22b.html

    2022

  7. [17]

    Solving k-center clustering (with outliers) in mapreduce and streaming, almost as accurately as sequentially

    Matteo Ceccarello, Andrea Pietracaprina, and Geppino Pucci. Solving k-center clustering (with outliers) in mapreduce and streaming, almost as accurately as sequentially. Proc. VLDB Endow. , 12(7):766--778, 2019. URL: http://www.vldb.org/pvldb/vol12/p766-ceccarello.pdf

    2019

  8. [18]

    MapReduce : Simplified data processing on large clusters

    Jeffrey Dean and Sanjay Ghemawat. MapReduce : Simplified data processing on large clusters. Communications of the ACM , 51(1):107--113, 2008. https://doi.org/10.1145/1327452.1327492 doi:10.1145/1327452.1327492

    2008

  9. [19]

    Fast clustering using MapReduce

    Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using MapReduce . In KDD , pages 681--689, 2011. https://doi.org/10.1145/2020408.2020515 doi:10.1145/2020408.2020515

    2011

  10. [20]

    Mirrokni, and Peilin Zhong

    Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, and Peilin Zhong. Massively parallel and dynamic algorithms for minimum size clustering. In SODA , pages 1613--1660. SIAM, 2022. https://doi.org/10.1137/1.9781611977073.66 doi:10.1137/1.9781611977073.66

    2022 doi

  11. [21]

    Scattering and sparse partitions, and their applications

    Arnold Filtser. Scattering and sparse partitions, and their applications. ACM Transactions on Algorithms , 20(4):30:1--30:42, 2024. https://doi.org/10.1145/3672562 doi:10.1145/3672562

    2024 doi

  12. [22]

    Improved MPC algorithms for MIS , matching, and coloring on trees and beyond

    Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC algorithms for MIS , matching, and coloring on trees and beyond. In DISC , pages 34:1--34:18, 2020. https://doi.org/10.4230/LIPICS.DISC.2020.34 doi:10.4230/LIPICS.DISC.2020.34

    2020 doi

  13. [23]

    Massively parallel algorithms, 2019

    Mohsen Ghaffari. Massively parallel algorithms, 2019. Lecture Notes from ETH Z\"urich. URL: http://people.csail.mit.edu/ghaffari/MPA19/Notes/MPA.pdf

    2019

  14. [24]

    Distributed graph algorithms, 2022

    Mohsen Ghaffari. Distributed graph algorithms, 2022. Lecture Notes from MIT. URL: https://people.csail.mit.edu/ghaffari/DA22/Notes/DGA.pdf

    2022

  15. [26]

    Gonzalez

    Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science , 38:293--306, 1985. https://doi.org/10.1016/0304-3975(85)90224-5 doi:10.1016/0304-3975(85)90224-5

    1985 doi

  16. [27]

    Massively parallel ruling set made deterministic

    Jeff Giliberti and Zahra Parsaeian. Massively parallel ruling set made deterministic. In DISC , pages 29:1--29:21, 2024. https://doi.org/10.4230/LIPICS.DISC.2024.29 doi:10.4230/LIPICS.DISC.2024.29

    2024 doi

  17. [28]

    Goodrich, Nodari Sitchinava, and Qin Zhang

    Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the MapReduce framework. In ISAAC , pages 374--383, 2011. https://arxiv.org/abs/1101.1902 arXiv:1101.1902

    2011 arXiv

  18. [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 SODA , pages 1636--1653, 2019. https://doi.org/10.1137/1.9781611975482.99 doi:10.1137/1.9781611975482.99

    2019 doi

  19. [30]

    No, coreset, no cry

    Sariel Har - Peled. No, coreset, no cry. In FSTTCS , pages 324--335, 2004. https://doi.org/10.1007/978-3-540-30538-5\_27 doi:10.1007/978-3-540-30538-5\_27

    2004 doi

  20. [31]

    On coresets for k -means and k -median clustering

    Sariel Har - Peled and Soham Mazumdar. On coresets for k -means and k -median clustering. In STOC , pages 291--300, 2004. https://doi.org/10.1145/1007352.1007400 doi:10.1145/1007352.1007400

    2004

  21. [32]

    Hochbaum and David B

    Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k -center problem. Mathematics of Operations Research , 10(2):180--184, 1985. https://doi.org/10.1287/moor.10.2.180 doi:10.1287/moor.10.2.180

    1985 doi

  22. [33]

    Hochbaum and David B

    Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM , 33(3):533--550, 1986. https://doi.org/10.1145/5925.5933 doi:10.1145/5925.5933

    1986

  23. [34]

    Almost optimal massively parallel algorithms for k -center clustering and diversity maximization

    Alireza Haqi and Hamid Zarrabi - Zadeh. Almost optimal massively parallel algorithms for k -center clustering and diversity maximization. In SPAA , pages 239--247, 2023. https://doi.org/10.1145/3558481.3591077 doi:10.1145/3558481.3591077

    2023

  24. [35]

    Dryad: Distributed data-parallel programs from sequential building blocks

    Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: Distributed data-parallel programs from sequential building blocks. In EuroSys , pages 59--72, 2007. https://doi.org/10.1145/1272996.1273005 doi:10.1145/1272996.1273005

    2007

  25. [36]

    Massively parallel computation: Algorithms and applications

    Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, and Sergei Vassilvitskii. Massively parallel computation: Algorithms and applications. Foundations and Trends in Optimization , 5(4):340--417, 2023. https://doi.org/10.1561/2400000025 doi:10.1561/2400000025

    2023 doi

  26. [37]

    Brief announcement: Fast and better distributed mapreduce algorithms for k -center clustering

    Sungjin Im and Benjamin Moseley. Brief announcement: Fast and better distributed mapreduce algorithms for k -center clustering. In SPAA , pages 65--67, 2015. https://doi.org/10.1145/2755573.2755607 doi:10.1145/2755573.2755607

    2015

  27. [38]

    Pemmaraju, and Ajitanshu Singh

    Hongyan Ji, Kishore Kothapalli, Sriram V. Pemmaraju, and Ajitanshu Singh. Fast deterministic massively parallel ruling sets algorithms. In ICDCN , pages 152--160, 2025. https://doi.org/10.1145/3700838.3700872 doi:10.1145/3700838.3700872

    2025

  28. [39]

    Extensions of Lipschitz maps into a Hilbert space

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

    1984 doi

  29. [40]

    Universal approximations for TSP , Steiner tree, and set cover

    Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for TSP , Steiner tree, and set cover. In STOC , pages 386--395, 2005. https://doi.org/10.1145/1060590.1060649 doi:10.1145/1060590.1060649

    2005

  30. [41]

    Massively parallel algorithms for high-dimensional Euclidean minimum spanning tree

    Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Massively parallel algorithms for high-dimensional Euclidean minimum spanning tree. In SODA , pages 3960--3996. SIAM, 2024. https://doi.org/10.1137/1.9781611977912.139 doi:10.1137/1.9781611977912.139

    2024 doi

  31. [42]

    Karloff, Siddharth Suri, and Sergei Vassilvitskii

    Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce . In SODA , pages 938--948, 2010. https://doi.org/10.1137/1.9781611973075.76 doi:10.1137/1.9781611973075.76

    2010 doi

  32. [43]

    Improved approximation algorithm for the distributed lower-bounded k -center problem

    Ting Liang, Qilong Feng, Xiaoliang Wu, Jinhui Xu, and Jianxin Wang. Improved approximation algorithm for the distributed lower-bounded k -center problem. In TAMC , pages 309--319, 2024. https://doi.org/10.1007/978-981-97-2340-9\_26 doi:10.1007/978-981-97-2340-9\_26

    2024 doi

  33. [44]

    A simple parallel algorithm for the maximal independent set problem

    Michael Luby. A simple parallel algorithm for the maximal independent set problem. In STOC , pages 1--10. ACM , 1985. https://doi.org/10.1145/22145.22146 doi:10.1145/22145.22146

    1985

  34. [45]

    Kusner, Wenlin Chen, Kilian Q

    Gustavo Malkomes, Matt J. Kusner, Wenlin Chen, Kilian Q. Weinberger, and Benjamin Moseley. Fast distributed k -center clustering with outliers on massive data. In NIPS , pages 1063--1071, 2015. URL: https://proceedings.neurips.cc/paper/2015/hash/8fecb20817b3847419bb3de39a609af...

    2015

  35. [46]

    Round compression for parallel graph algorithms in strongly sublinear space

    Krzysztof Onak. Round compression for parallel graph algorithms in strongly sublinear space. arXiv preprint arXiv:1807.08745 , 2018. https://arxiv.org/abs/1807.08745 arXiv:1807.08745

    2018 arXiv

  36. [47]

    Empirical Processes: Theory and Applications , chapter 4: Packing and Covering in Euclidean Spaces, pages 14--20

    David Pollard. Empirical Processes: Theory and Applications , chapter 4: Packing and Covering in Euclidean Spaces, pages 14--20. IMS, 1990. https://doi.org/10.1214/cbms/1462061091 doi:10.1214/cbms/1462061091

    1990

  37. [48]

    Polylogarithmic-time deterministic network decomposition and distributed derandomization

    V \'a clav Rozho n and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In STOC , pages 350--363, 2020. https://doi.org/10.1145/3357713.3384298 doi:10.1145/3357713.3384298

    2020

  38. [49]

    Tim Roughgarden, Sergei Vassilvitski, and Joshua R. Wang. Shuffles and circuits (on lower bounds for modern parallel computation). Journal of the ACM , 65(6):41:1--41:24, November 2018. https://doi.org/10.1145/3232536 doi:10.1145/3232536

    2018 doi

  39. [50]

    An optimal maximal independent set algorithm for bounded-independence graphs

    Johannes Schneider and Roger Wattenhofer. An optimal maximal independent set algorithm for bounded-independence graphs. Distributed Computing , 22(5-6):349--361, 2010. URL: https://doi.org/10.1007/s00446-010-0097-1, https://doi.org/10.1007/S00446-010-0097-1 doi:10.1007/S00446-...

    2010 doi

  40. [51]

    Hadoop: The Definitive Guide

    Tom White. Hadoop: The Definitive Guide . O'Reilly, 4th edition, 2015. URL: https://www.oreilly.com/library/view/hadoop-the-definitive/9781491901687/

    2015

  41. [52]

    Franklin, Scott Shenker, and Ion Stoica

    Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. In HotCloud , 2010. URL: https://www.usenix.org/conference/hotcloud-10/spark-cluster-computing-working-sets

    2010

Pith tools

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