Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs

Jakub {\L}\k{a}cki; Slobodan Mitrovi\'c; Srikkanth Ramachandran; Wen-Horng Sheu

REVIEW 3 major objections 5 minor 29 references

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs

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

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

Pith's one-line read A new MPC algorithm computes near-optimal allocations on sparse graphs in $O(\sqrt{\log\lambda}\log\log\lambda)$ rounds, without knowing $\lambda$.

desk verdict The LOCAL analysis is clean and likely correct, but the MPC algorithm rests on a false sampling lemma and a missing (4τ+1) factor, so the headline bound is not established. read the letter →

arxiv 2506.04524 v1 pith:7Z5BHOZJ submitted 2025-06-05 cs.DS

Jakub {L}ącki , Slobodan Mitrović , Srikkanth Ramachandran , Wen-Horng Sheu This is my paper

classification cs.DS MSC 68W1568W2505C8568R10

keywords allocationproblemb-matchingMassivelyParallelComputationarboricityLOCALmodelproportionalgraphsparsificationsublinearspace

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 targets the allocation problem: given a bipartite graph with capacities on the right-hand vertices, find the largest set of edges that respects those capacities. It proves that a known proportional-allocation LOCAL algorithm, previously analyzed as $O(\log n)$ rounds, actually converges in $O(\log \lambda)$ rounds where $\lambda$ is the graph's arboricity---the minimum number of forests into which its edges can be partitioned. Translating this analysis to the Massively Parallel Computation (MPC) model with sublinear per-machine memory gives an algorithm that runs in $O_\epsilon(\sqrt{\log \lambda}\log\log \lambda)$ rounds, uses $\tilde{O}(\lambda n)$ total memory, achieves a $1+\epsilon$ approximation, and does not need to know $\lambda$ in advance. This is the first $o(\log n)$-round sublinear-MPC algorithm for constant-approximate allocation on low-arboricity graphs, so it brings allocation close to the round bounds previously achieved only for matching.

What carries the argument

The machine carrying the argument is the $\beta$-value proportional update together with the level-set decomposition $L_j=\{v:\beta_v=(1+\epsilon)^j\beta_{\min}\}$. The critical identity is that after $\tau$ rounds every edge from $N(L_{2\tau})$ into $L_0$ contributes at most $1/(1+\epsilon)^{2\tau-2}$ of its neighbor's allocation, so if too much weight flows into $L_0$, the subgraph induced by $N(L_{2\tau})\cup L_0$ must contain $\Omega(|N(L_{2\tau})|(1+\epsilon)^{2\tau})$ edges, contradicting the arboricity upper bound. This converts a density bound into a round bound. For MPC, exact sums are replaced by estimates from $t=(1+\epsilon)^{2B}\epsilon^{-5}\log n$ uniform samples per $\beta$-level group per vertex, and graph exponentiation---doubling the neighborhood radius in each round---collects $B$-hop balls whose volume is controlled by the sample bound; choosing $B\approx \sqrt{\log\lambda}$ makes total memory $\tilde{O}(\lambda n)$.

What would settle it

Take a star with arboricity $\lambda=1$, center capacity $n-1$, and priorities arranged so one $\beta$-level group contains a single neighbor with the maximum possible weight while all other neighbors are in the lowest group; run algorithm 2 with the stated sample size $t$. If the $t$ uniform samples miss that single high-weight element---probability roughly $1-t/(n-1)$---the estimated center aggregate is off by more than the promised $1+4\epsilon$ factor, and the output should violate the claimed $2+16\epsilon$ approximation for large $n$ and constant small $\epsilon$.

Watch

Extended reading notes

Core claim

The central discovery is that the convergence speed of the proportional allocation algorithm depends on arboricity, not on graph size. The algorithm assigns each right vertex a priority $\beta_v$, initially 1; in each round each left vertex splits its value among neighbors in proportion to their $\beta$ values, and each right vertex raises or lowers $\beta_v$ by a factor $1+\epsilon$ when its load is too low or too high. After $\tau$ rounds the right vertices fall into $2\tau+1$ level sets $L_0,\dots,L_{2\tau}$ by $\beta$ value. The paper shows that if the algorithm has not yet produced a $(2+O(\epsilon))$-approximation, then almost all units sent from $N(L_{2\tau})$ land in $L_0$; because $\beta$ values at $L_{2\tau}$ dominate those at $L_0$ by $(1+\epsilon)^{2\tau}$, each such edge can carry at most $\epsilon/(4\lambda)$, and the arboricity bound forces fewer than $2\lambda|N(L_{2\tau})|$ such edges. That contradiction yields $\tau\approx \log_{1+\epsilon}(4\lambda/\epsilon)+1$ rounds. In MPC the same dynamics are simulated over blocks of $B$ rounds using uniform samples from each $\beta$-level group per vertex; graph exponentiation then collects the $B$-hop influencing neighborhood of every vertex, and a detectable stopping condition lets the algorithm double its guess of $\lambda$ until it succeeds.

Load-bearing premise

The MPC correctness argument rests on the claim that independent uniform samples from each $\beta$-value group estimate the sums needed in every round to within a $1+O(\epsilon)$ factor; the proof sketch does not fully control the possibly large contribution of a single high-weight element in a small group, and the per-vertex degree bound omits the factor from the number of $\beta$-level groups, so the claimed ball-size and memory bounds are not established.

Editorial extensions

If this is right

On graphs of arboricity $\lambda$, allocation can now be solved in $\tilde{O}(\sqrt{\log\lambda}\log\log\lambda)$ MPC rounds with sublinear per-machine memory, improving on the previous $O(\log n)$ translation of the local algorithm.
The underlying LOCAL protocol runs in $O_\epsilon(\log\lambda)$ rounds and yields a $2+\epsilon$ fractional allocation deterministically; boosting it to a $1+\epsilon$ integral allocation preserves the same round complexity.
Because the algorithm does not need to know $\lambda$, it can be run on any input; the stopping test that replaces $\lambda$ costs only $O(1)$ MPC rounds.
The total memory $\tilde{O}(\lambda n)$ is near-linear for uniformly sparse graphs, so the algorithm also works in the near-linear-space MPC regime, not only the sublinear one.
The result avoids capacity-copy reductions that blow up arboricity (a star with capacity $n-1$ becomes a complete bipartite graph), so the sparse-structure guarantee is preserved.

Reading between the lines

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

The same block-simulation idea likely extends to bipartite $b$-matching: each invocation of the boosting construction of [GGM22] works on a subgraph of arboricity at most $\lambda$, so closing the small-group sampling gap would give an $o(\log n)$-round sublinear-MPC algorithm for $b$-matching on sparse graphs, a question the paper leaves open.
The 'guess $\lambda$ by doubling $\sqrt{\log\lambda}$ and test a stopping condition' strategy is portable: any density-controlled local algorithm whose termination can be verified in $O(1)$ MPC rounds can run without knowing its density parameter at only constant factor overhead.
The per-group uniform sampling in lemma 11 is likely suboptimal for small groups; an importance-sampling or heavy-element correction could reduce the sample count and shrink the per-vertex degree bound and memory footprint beyond the stated $\tilde{O}(\lambda n)$.

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.

Desk Editor's Note

read the letter

Quick take: the LOCAL result is real; the MPC result is not. I read Section 4 and Theorem 9 carefully, and the arboricity argument checks out: after τ ≈ log_{1+ϵ}(4λ/ϵ) rounds, the only way the algorithm can miss a 2+O(ϵ) approximation is if a large fraction of N(L_{2τ}) is served by L0, and that forces a subgraph of density ~λ that cannot exist. The proof of Lemma 7 and the use of capacity sums are sound. This is a genuine improvement over the O(log n) analysis of AZM18 for low-arboricity graphs. I would be comfortable citing that part.

The MPC section is where it falls apart. Lemma 11 as stated is false. The proof splits into "small groups contribute little" and "large groups concentrate," but those two cases are not exhaustive, and the first case fails exactly when small groups carry a large total mass. A single high-weight element can be missed with high probability and the rescaled estimate is off by ~n/t^2. That is not just a gap in the proof; it is a counterexample to the claim. Since Lemma 11 is the concentration step that justifies the whole sampling scheme, the correctness of Algorithm 2 is not established.

The stress-test note about the (4τ+1) factor is also correct. Algorithm 2 samples t edges from each of 4τ+1 β-level groups per round, so the per-vertex degree in H_r is (4τ+1)t, not the d printed in the text. The B-radius volume bound d^B then misses a factor of (4τ+1)^B, which enters as B log τ = Θ(√logλ · log logλ) in the exponent. For asymptotic λ this might be absorbable by the constant in B, but the paper does not supply the argument, and for moderate λ the slack in eq. (4) is gone.

The rest of the MPC description is also under-specified: the graph exponentiation step is invoked as standard without saying whether the B-hop balls are taken in the union of the H_r or in each H_r separately, which affects the volume bound. These issues are fixable, but they require a real rewrite of Section 5 and Appendix A.

Verdict: send to a good venue, but only with the expectation of major revision. The LOCAL theorem is worth publishing on its own, and the MPC approach may be salvageable, but the current main theorem is not supported. The paper is aimed at the MPC and sublinear-algorithms crowd; a referee with a taste for checking sampling arguments will earn their keep.

Referee Report

3 major / 5 minor

Summary. The paper studies the allocation problem (a special case of b-matching on bipartite graphs with capacities only on one side) in the Massively Parallel Computation (MPC) model. The main claim is a (1+epsilon)-approximate allocation algorithm that runs in O_epsilon(sqrt(log lambda) log log lambda) MPC rounds, uses n^alpha local memory per machine and O~(lambda n) total memory, and does not require knowledge of the arboricity lambda. The proof route is: (i) a new analysis of the LOCAL algorithm of Agrawal, Zadimoghaddam, and Mirrokni [AZM18], showing that O_epsilon(log lambda) rounds suffice for a (2+epsilon)-approximate fractional allocation on graphs of arboricity lambda; (ii) an MPC simulation of O_epsilon(sqrt(log lambda)) of those LOCAL rounds via a graph-sparsification/ball-copying scheme in the style of Ghaffari and Uitto [GU19]; and (iii) a black-box application of the Ghaffari, Grunau, and Mitrovic [GGM22] framework to boost the approximation to 1+epsilon.

Significance. If the main result holds, it would be a meaningful step beyond the long-standing O(sqrt(log n))-round barrier for approximate matching in the sublinear MPC regime, specialized to graphs of low arboricity, and it would extend this progress from matching to the more general allocation problem. The LOCAL analysis in Section 4 is coherent and elegant: the arboricity argument in Theorem 9 bounding the edges between N(L_{2tau}) and L_0 is checkable and appears sound. The paper also explicitly addresses the issue of not knowing lambda, which is a genuine practical concern in this line of work. The principal weaknesses are in the MPC simulation section (Section 5): the sampling estimator as written is not the correct estimator for the stratified sampling procedure, the per-vertex degree bound omits a factor from the number of beta-level groups, and the sample-count parameters are not matched to the concentration lemma. These issues are load-bearing for the claimed round, memory, and correctness guarantees, but they appear to be fixable within the scope of the paper, so the appropriate decision is major revision rather than rejection.

major comments (3)

[Section 5, Algorithm 2, lines 3 and 5; Lemma 12] The estimator in line 5 is not compatible with the sampling process in line 3. Line 3 samples t edges uniformly at random from each level group L_x, so the resulting set N_{r,u} is a stratified sample whose sampling rate varies across groups; the ratio estimator |N_u|/|N_{r,u}| * sum_{v in N_{r,u}} beta_v is biased for beta_u = sum_{v in N_u} beta_v unless all groups have equal size. The correct estimator is sum_x (|L_x|/t) * sum_{v in sample_x} beta_v, with the appropriate min(t,|L_x|) adjustment when a group has fewer than t elements. As written, Lemma 12 does not follow from Lemma 11, and the equivalence argument in Appendix A.1 relies on Lemma 12. This is a central correctness issue for the MPC simulation.
[Section 5, paragraph defining d and Eq. (4)] The per-vertex degree bound d omits the factor (4tau+1) coming from the number of beta-level groups. Algorithm 2 samples t edges from each of the 4tau+1 groups L_x (x in [-2tau,2tau]) for every round index r in [0,B), so the degree of a vertex in each H_r is at most (4tau+1)*t, not t. This missing factor enters the condition d^B <= min{lambda, n^alpha} through B log(4tau+1) = Theta(sqrt(log lambda) log log lambda), and the paper gives no argument that the constant in Eq. (4) can be reduced to absorb this term while preserving B = Theta(sqrt(log lambda)). Consequently, the claimed n^alpha local memory and O~(lambda n) total memory bounds are not established as written. This is fixable by choosing the constant in Eq. (4) sufficiently small, but the proof needs to be supplied.
[Section 5, Algorithm 2 parameters and Lemma 12] The sample count in Algorithm 2 is not matched to Lemma 11. Lemma 11 with ratio t_ratio = (1+epsilon)^B requires s >= 20(1+epsilon)^{2B} log n / epsilon^4 samples per group, whereas Algorithm 2 sets t = (1+epsilon)^{2B} epsilon^{-5} log n. The ratio t/s equals epsilon/20, so for constant epsilon (for example epsilon = 1/4) the algorithm samples strictly fewer elements than the concentration lemma requires. The text in Section 5 also claims a total degree d = 20(1+epsilon)^{2B} log^2 n epsilon^{-5}, which does not follow from the stated Lemma 11 bound. The parameters need to be corrected and the derivation of d needs to be made explicit before Lemma 12 can be considered proven.

minor comments (5)

[Algorithm 2, line 3] The pseudocode iterates over 'each vertex w in V(G)' but then writes 'E_{r,v,x} <- Sample t edges from N_v cap L_x', using an undefined variable v; this should be N_w or the loop variable should be v.
[Section 5, notational overloading] The symbol beta_u is used both for the true sum beta_u = sum_{v in N_u} beta_v and for the estimated quantity in Algorithm 2, line 5. Using a distinct notation such as hat(beta)_u for the estimate would improve readability and avoid confusion in Lemma 12.
[Lemma 11, proof structure] The proof labels 'Case 1' and 'Case 2' as if they were alternatives, but the bound in 'Case 1' is actually unconditional given the choice of s, and 'Case 2' proves a concentration event. Rewriting the proof as a single argument would make the logic clearer.
[Eq. (4) and surrounding text] The text says 'we set B = B_epsilon/48' after Eq. (4), but Eq. (4) defines B_epsilon; please clarify the naming and the exact role of the factor 1/48 in the derivation of the ball-size bound.
[Introduction, related work] The abstract claims 'no o(log n) round algorithm for constant-approximate allocation was known in either LOCAL or sublinear MPC models for graphs with low arboricity'; the related-work discussion would benefit from explicitly contrasting with the matching-only result of Behnezhad et al. [BBD+19] to make the novelty precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new LOCAL analysis and MPC sparsification derive their bounds from arboricity and previously published frameworks, not from the target theorem.

full rationale

The paper's derivation chain is self-contained rather than circular. Theorem 9 proves the O(log lambda) LOCAL convergence by combining the external [AZM18] capacity/neighborhood upper bound with an arboricity-based edge count in the subgraph induced by N(L_{2tau}) and L_0; the arboricity lambda is an input graph property, not the output approximation or round bound, so the conclusion is not built into the premise. Lemma 11 is a standard concentration argument on a fixed sequence of values, and the sampling parameter t is set from the desired accuracy and the bounded multiplicative drift of beta-values, not from the final theorem. The MPC simulation is justified by an inductive equivalence between Algorithm 2 and the more flexible Algorithm 3 (Lemma 13), with parameters k_{v,r} chosen after the fact to match behavior; this is a correctness proof, not a definitional identity. The final boost from constant to 1+epsilon approximation composes the paper's 2+epsilon algorithm with the [GGM22] b-matching framework as a black box; although one coauthor is an author of [GGM22], that framework is a published external result with its own correctness argument and does not assume the present theorem, so invoking it is ordinary composition rather than circular support. The reviewer's concern about the omitted factor (4tau+1) in the per-vertex degree bound is a potential correctness gap in the memory analysis, not a circularity pattern: it concerns whether the stated ball-size bound is proved, not whether the claimed result is equivalent to its inputs by construction.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard arboricity facts, two cited frameworks (AZM18's level-set upper bound and GGM22's boosting), and the paper's new concentration lemma. No data-fitting parameters or invented entities are present.

free parameters (3)

phase length B = min{sqrt(alpha log n / (8 epsilon)), sqrt(log lambda / (8 epsilon))} / 48
Chosen analytically so the sampled B-hop ball fits in one machine and total memory is O~(lambda n); not fitted to data.
sample count s per level = 20 (1+epsilon)^{2B} log n / epsilon^4
Set by Lemma 11 to guarantee 1+O(epsilon) concentration of estimated sums; a design parameter rather than an empirical fit.
total LOCAL rounds tau = log_{1+epsilon}(4 lambda / epsilon) + 1
Derived in Theorem 9 from the arboricity argument; not a free empirical parameter.

assumptions (4)

standard math Every subgraph H of a graph with arboricity lambda has at most lambda times |V(H)| edges.
Used in Theorem 9 Case 2 to bound the number of edges between N(L_{2tau}) and L0.
domain assumption AZM18 Claim 1: OPT is at most the capacity of the union of low levels plus the neighborhood of high levels.
Quoted from [AZM18] and used as Lemma 8 and eq. (10) without proof.
domain assumption The GGM22 framework preserves augmenting walks and can boost a constant-approximation b-matching algorithm to (1+epsilon) with O_epsilon(1) invocations.
Invoked in Section 6 and Appendix B; the adaptation to allocation is asserted but not fully proven.
ad hoc to paper The concentration lemma (Lemma 11) holds as stated with s = 20 t^2 log n / epsilon^4 samples.
This is the paper's new sampling lemma; the proof has a gap for small groups, so the claim is a load-bearing assumption rather than an established theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs." pith.science (2026). https://pith.science/paper/7Z5BHOZJ

@misc{pith2026250604524,
  author       = {Pith},
  title        = {Pith review of: Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7Z5BHOZJ}},
  note         = {Machine review of arXiv:2506.04524}
}

abstract

We study the allocation problem in the Massively Parallel Computation (MPC) model. This problem is a special case of $b$-matching, in which the input is a bipartite graph with capacities greater than $1$ in only one part of the bipartition. We give a $(1+\epsilon)$ approximate algorithm for the problem, which runs in $\tilde{O}(\sqrt{\log \lambda})$ MPC rounds, using sublinear space per machine and $\tilde{O}(\lambda n)$ total space, where $\lambda$ is the arboricity of the input graph. Our result is obtained by providing a new analysis of a LOCAL algorithm by Agrawal, Zadimoghaddam, and Mirrokni [ICML 2018], which improves its round complexity from $O(\log n)$ to $O(\log \lambda)$. Prior to our work, no $o(\log n)$ round algorithm for constant-approximate allocation was known in either LOCAL or sublinear space MPC models for graphs with low arboricity.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

[1]

Coresets meet edcs: algorithms for matching and vertex cover on massive graphs

Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1616--1635. SIAM, 2019

work page 2019
[2]

Distributed load balancing: A new framework and improved guarantees

Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam. Distributed load balancing: A new framework and improved guarantees. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2021

work page 2021
[3]

Online ad allocation in bounded-degree graphs

Susanne Albers and Sebastian Schubert. Online ad allocation in bounded-degree graphs. In Kristoffer Arnsfelt Hansen, Tracy Xiao Liu, and Azarakhsh Malekian, editors, Web and Internet Economics - 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings , volume 13778 of Lecture Notes in Computer Science , pages 60--77. Spr...

work page 2022
[4]

Mirrokni

Shipra Agrawal, Morteza Zadimoghaddam, and Vahab S. Mirrokni. Proportional allocation: Simple, distributed, and diverse matching with high entropy. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm \" a ssan, Stockholm, Sweden, July 10-15, 2018 , volume 80 of Proceed...

work page 2018
[5]

Karp, and Jara Uitto

Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. Massively parallel computation of matching and mis in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing , PODC '19, page 481–490, New York, NY, USA, 2019. Association for Computing Machinery

work page 2019
[6]

Exponentially faster massively parallel maximal matching

Soheil Behnezhad, Mohammad Taghi Hajiaghayi, and David G Harris. Exponentially faster massively parallel maximal matching. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1637--1649. IEEE, 2019

work page 2019
[7]

Balseiro, Haihao Lu, and Vahab Mirrokni

Santiago R. Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. , 71(1):101--119, 2023

work page 2023
[8]

Component stability in low-space massively parallel computation

Artur Czumaj, Peter Davies, and Merav Parter. Component stability in low-space massively parallel computation. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , PODC'21, page 481–491, New York, NY, USA, 2021. Association for Computing Machinery

work page 2021

Show all 29 references

[9]

Round compression for parallel matching algorithms

Artur Czumaj, Jakub a cki, Aleksander M a dry, Slobodan Mitrovi \'c , Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 471--484, 2018

2018
[10]

Parallel set cover and hypergraph matching via uniform random sampling

Laxman Dhulipala, Michael Dinitz, Jakub a cki, and Slobodan Mitrovi \'c . Parallel set cover and hypergraph matching via uniform random sampling. In 38th International Symposium on Distributed Computing (DISC 2024) , pages 19--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Infor...

2024
[11]

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

2008
[12]

Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A

Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM , 66(1):7:1--7:41, 2019

2019
[13]

Dickerson, Karthik A

John P. Dickerson, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Trans. Econ. Comput. , 9(3), June 2021

2021
[14]

Online ad assignment with free disposal

Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin P \'a l. Online ad assignment with free disposal. In International workshop on internet and network economics , pages 374--385. Springer, 2009

2009
[15]

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 Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020) , volume 179 of Leibniz International Proceedings in Informat...

2020
[16]

Improved massively parallel computation algorithms for mis, matching, and vertex cover

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovi\' c , and Ronitt Rubinfeld. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing , PODC '18,...

2018
[17]

Massively parallel algorithms for b-matching

Mohsen Ghaffari, Christoph Grunau, and Slobodan Mitrovi \'c . Massively parallel algorithms for b-matching. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , pages 35--44, 2022

2022
[18]

Conditional hardness results for massively parallel computation from distributed lower bounds

Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November...

2019
[19]

Sorting, searching, and simulation in the mapreduce framework

Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In International Symposium on Algorithms and Computation , pages 374--383. Springer, 2011

2011
[20]

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 Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San ...

2019
[21]

Mirrokni, and Morteza Zadimoghaddam

Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Online stochastic weighted matching: Improved approximation algorithms. In Ning Chen, Edith Elkind, and Elias Koutsoupias, editors, Internet and Network Economics - 7th International Workshop, WINE 2011, Singapor...

2011
[22]

A model of computation for mapreduce

Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages 938--948. SIAM, 2010

2010
[23]

Scalable auction algorithms for bipartite maximum matching problems

Quanquan C Liu, Yiduo Ke, and Samir Khuller. Scalable auction algorithms for bipartite maximum matching problems. arXiv preprint arXiv:2307.08979 , 2023

2023 arXiv
[24]

Filtering: a method for solving graph problems in mapreduce

Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in mapreduce. In Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures , pages 85--94, 2011

2011
[25]

Brief announcement: Exponential speed-up of local algorithms using non-local communication

Christoph Lenzen and Roger Wattenhofer. Brief announcement: Exponential speed-up of local algorithms using non-local communication. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing , pages 295--296, 2010

2010
[26]

Adwords and generalized online matching

Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM) , 54(5):22--es, 2007

2007
[27]

Optimal online assignment with forecasts

Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. Optimal online assignment with forecasts. In Proceedings of the 11th ACM conference on Electronic commerce , pages 109--118, 2010

2010
[28]

Socially enabled wireless networks: Resource allocation via bipartite graph matching

Li Wang, Huaqing Wu, Wei Wang, and Kwang-Cheng Chen. Socially enabled wireless networks: Resource allocation via bipartite graph matching. IEEE Communications Magazine , 53(10):128--135, 2015

2015
[29]

Sivakumar

Goran Zuzic, Di Wang, Aranyak Mehta, and D. Sivakumar. Learning robust algorithms for online allocation problems using adversarial training. CoRR , abs/2010.08418, 2020

2010 arXiv

Pith tools

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

[1] [1]

Coresets meet edcs: algorithms for matching and vertex cover on massive graphs

Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1616--1635. SIAM, 2019

work page 2019

[2] [2]

Distributed load balancing: A new framework and improved guarantees

Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam. Distributed load balancing: A new framework and improved guarantees. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2021

work page 2021

[3] [3]

Online ad allocation in bounded-degree graphs

Susanne Albers and Sebastian Schubert. Online ad allocation in bounded-degree graphs. In Kristoffer Arnsfelt Hansen, Tracy Xiao Liu, and Azarakhsh Malekian, editors, Web and Internet Economics - 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings , volume 13778 of Lecture Notes in Computer Science , pages 60--77. Spr...

work page 2022

[4] [4]

Mirrokni

Shipra Agrawal, Morteza Zadimoghaddam, and Vahab S. Mirrokni. Proportional allocation: Simple, distributed, and diverse matching with high entropy. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm \" a ssan, Stockholm, Sweden, July 10-15, 2018 , volume 80 of Proceed...

work page 2018

[5] [5]

Karp, and Jara Uitto

Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. Massively parallel computation of matching and mis in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing , PODC '19, page 481–490, New York, NY, USA, 2019. Association for Computing Machinery

work page 2019

[6] [6]

Exponentially faster massively parallel maximal matching

Soheil Behnezhad, Mohammad Taghi Hajiaghayi, and David G Harris. Exponentially faster massively parallel maximal matching. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1637--1649. IEEE, 2019

work page 2019

[7] [7]

Balseiro, Haihao Lu, and Vahab Mirrokni

Santiago R. Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. , 71(1):101--119, 2023

work page 2023

[8] [8]

Component stability in low-space massively parallel computation

Artur Czumaj, Peter Davies, and Merav Parter. Component stability in low-space massively parallel computation. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , PODC'21, page 481–491, New York, NY, USA, 2021. Association for Computing Machinery

work page 2021