Pith. sign in

REVIEW 3 minor 17 references

On the Assadi Liu Tarjan Auction Algorithm for Bipartite Matching: Simplification, Alternative Analysis, and Hard Instance

T0 review · 0 major / 3 minor · reviewed 2026-07-10 · grok-4.5

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

Pith's one-line read The Assadi–Liu–Tarjan auction matching algorithm works without freezing and needs Θ(1/ε²) maximal matchings even on a path.

desk verdict Clean simplification of ALT plus a matching path lower bound; the constant 49 is cosmetic and the math holds. read the letter →

arxiv 2607.07439 v2 pith:XM7BHMJJ submitted 2026-07-08 cs.DS

Christian Konrad , Kheeran K. Naidu , Archie Walton , Eric Wang This is my paper · ORCID
classification cs.DS MSC 68W2505C7068Q25
keywords bipartitematchingauctionalgorithmmaximalmatchingsaugmentingpathsmulti-passstreamingapproximationalgorithmshardinstances
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 re-examines a well-known auction-style algorithm that finds a near-maximum matching in bipartite graphs by repeatedly computing maximal matchings. The original algorithm freezes any vertex that has been rematched too many times so that it never changes partners again. The authors prove that the freezing rule can be deleted entirely: the same (1−ε)-guarantee is obtained after a fixed number of iterations that depends only on ε. They also replace the original potential-function argument with a direct analysis that links the number of times a vertex has changed partners to the length of any remaining augmenting path. Finally they exhibit a simple path graph on which the algorithm is forced into long cycles of rematching, proving that Ω(1/ε²) iterations are sometimes necessary. Together these results clean the algorithm, explain why it works, and show that its quadratic dependence on 1/ε is tight.

What carries the argument

The counter c(b) that records how many times each right-hand vertex has been rematched; Lemma 1 proves that any augmenting path through an unmatched left-hand vertex a has length at least 2·c_min(a)+1, so large counters force long paths and therefore a good approximation.

What would settle it

Run the simplified algorithm (no freezing) on the path graphs of Section 4 with ε = 1/(3x) and count the number of maximal-matching steps until a maximum matching appears; if the count is o(x²) for large x then the claimed lower bound fails.

Watch

Extended reading notes

Core claim

Removing the artificial freezing mechanism from the Assadi–Liu–Tarjan algorithm still yields a (1−ε)-approximate maximum bipartite matching after O(1/ε²) maximal-matching computations, and the same bound is tight already on path graphs.

Load-bearing premise

The concrete constant 49 that appears in the iteration bound is chosen only so that two counting arguments produce a numerical contradiction; a tighter analysis of the same lemmas could replace it by a smaller universal constant.

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

0 major / 3 minor

Summary. The paper revisits the Assadi–Liu–Tarjan (ALT) auction algorithm for (1-ε)-approximate maximum bipartite matching. It removes the original freezing mechanism (vertices rematched Θ(1/ε) times stay fixed), shows that the resulting Algorithm 1 still returns a (1-ε)-approximation after 49/ε² maximal-matching computations (Theorem 3), supplies an alternative analysis based on lower-bounding the length of augmenting paths by the counters c_min (Lemma 1 and Corollary 2), and constructs an explicit path-graph hard instance that forces Ω(1/ε²) iterations even without freezing (Section 4, Corollary 5). The analysis re-uses only elementary properties of the counters and a simple double-counting argument that produces a numerical contradiction once the iteration budget is large enough.

Significance. The work cleanly simplifies a state-of-the-art multi-pass streaming algorithm, replaces an opaque potential-function argument with a transparent augmenting-path interpretation, and supplies the first matching lower-bound instance. Because the same lemmas underwrite both the upper and lower bounds, the asymptotic Θ(1/ε²) complexity of the maximal-matching approach is now tightly characterised. The removal of freezing also makes the algorithm adaptive in ε, a practical improvement for streaming and MPC implementations. These contributions are solid, self-contained, and of clear interest to the streaming and matching communities.

minor comments (3)
  1. The concrete constant 49 that appears in Algorithm 1 and in the proof of Theorem 3 is an artefact of the particular thresholds 2/ε, 6/ε, ε/3 and ε/6 chosen for the counting arguments. A short remark that any sufficiently large universal constant works, or a brief optimisation of the thresholds, would make the presentation cleaner.
  2. In the hard-instance construction (Section 4) the four “setup” rounds and the subsequent sweep invariants are carefully maintained, yet a single figure that shows the cost vector after a complete rightward-plus-leftward sweep would help the reader verify the arithmetic.
  3. A few typographical inconsistencies remain (e.g., “c min(a)” versus “c_min(a)”, occasional missing spaces around “Θ(1/ε)”). They do not affect correctness but should be cleaned for the final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; self-contained combinatorial analysis of matching algorithm with independent hard-instance construction.

full rationale

The paper's central claims (Theorem 3 that the simplified Algorithm 1 yields a (1-ε)-approximation after 49/ε^{2} maximal matchings, and Corollary 5 that Ω(1/ε^{2}) iterations are necessary) rest on an original Lemma 1 relating c_min values to augmenting-path lengths in M ⊕ OPT, followed by two elementary counting arguments that produce a numerical contradiction once the iteration budget is fixed. These arguments use only the algorithm's own invariants (P1–P3) and the definition of the demand subgraph; they do not invoke fitted parameters, self-referential definitions, or load-bearing self-citations. The hard-instance path construction (Section 4) is independent of the upper-bound analysis and never relies on the freezing mechanism for the chosen ε. Citations to Assadi et al. merely identify the original algorithm being simplified; the new analysis and lower bound stand alone. No step reduces by construction to its own inputs.

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

Standard bipartite-matching facts (augmenting paths, size of maximum matching) plus the elementary properties P1–P3 of the ALT process. The only non-standard numerical choices are the concrete thresholds 2/ε, 6/ε and the iteration count 49/ε² that make the double-counting contradictions fire; they are analysis artefacts, not free parameters fitted to data.

free parameters (1)
  • iteration multiplier 49
    Chosen in Algorithm 1 so that 49/ε² – 36/ε² = 13/ε² yields a contradiction with the 2/ε budget on min-cost increases; any sufficiently large constant works.
assumptions (3)
  • standard math In a bipartite graph a matching is maximum if and only if there is no M-augmenting path (Berge).
    Used throughout Section 3 to relate unmatched OPT vertices to path lengths.
  • domain assumption Once a B-vertex is matched it stays matched forever (Property P1).
    Immediate from the update rule of Algorithm 1; invoked in the progress counting of Theorem 3.
  • domain assumption c_min(a) never decreases and increases by 1 whenever an unmatched a stays unmatched (Properties P2–P3).
    Direct from the definition of the demand subgraph; used in Lemma 1 and the final contradiction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Assadi Liu Tarjan Auction Algorithm for Bipartite Matching: Simplification, Alternative Analysis, and Hard Instance." pith.science (2026). https://pith.science/paper/XM7BHMJJ

@misc{pith2026260707439,
  author       = {Pith},
  title        = {Pith review of: On the Assadi Liu Tarjan Auction Algorithm for Bipartite Matching: Simplification, Alternative Analysis, and Hard Instance},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XM7BHMJJ}},
  note         = {Machine review of arXiv:2607.07439}
}
abstract

Assadi, Liu, and Tarjan [SOSA'21] gave an auction algorithm that outputs a $(1-\epsilon)$-approximation to Maximum Matching in bipartite graphs. Their algorithm computes a sequence of $O(\frac{1}{\epsilon^2})$ maximal matchings in subgraphs of the input graph and can be implemented in the multi-pass streaming setting with $O(\frac{1}{\epsilon^2})$ passes in a straightforward manner, which constitutes the state-of-the-art pass/approximation trade-off result in the multi-pass streaming setting. Their analysis uses tools from combinatorial auctions and, at its heart, relies on a clever potential function argument. Their proof, however, provides only limited insight into the inner workings of the algorithm. In this paper, we revisit the ALT-algorithm and present the following contributions. Simplification: The ALT-algorithm is built upon a freezing mechanism where vertices on one side of the bipartition that have already been rematched $\Theta(\frac{1}{\epsilon})$ times over the course of the algorithm remain matched to their current partner forever. We show that this mechanism is in fact unnecessary, i.e., no special treatment of such vertices is needed. Alternative Analysis: We give an alternative analysis of the algorithm that is based on augmenting paths. Our analysis allows for a reinterpretation as one that follows the traditional approach of searching for and eliminating augmenting paths. Our analysis also copes with the removal of the freezing mechanism in a natural way, whereas the analysis of Assadi et al. strictly depends on its use. Hard Instance: We provide the first hard instance on which the algorithm requires $\Omega(\frac{1}{\epsilon^2})$ iterations/maximal matching computations. The instance is a simple path graph, where we exhibit a cyclic behaviour that prevents fast progress.

Figures

Figures reproduced from arXiv: 2607.07439 by the authors.

Figure 1
Figure 1. The state of a path on 16 vertices after each setup round. Edges in red are part of the [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. An example of a path during stages of a sweep. Edges in red are part of the matching. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Linear programming in the semi-streaming model with ap- plication to the maximum matching problem.Inf

    Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with ap- plication to the maximum matching problem.Inf. Comput., 222:59–79, 2013. URL:https: //doi.org/10.1016/j.ic.2012.10.006,doi:10.1016/J.IC.2012.10.006

    work page doi:10.1016/j.ic.2012.10.006 2013

  2. [2]

    Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints.ACM Trans

    Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints.ACM Trans. Parallel Comput., 4(4):17:1– 17:40, 2018.doi:10.1145/3154855

    work page doi:10.1145/3154855 2018

  3. [3]

    A simple (1 -ϵ)-approximation semi-streaming algorithm for maximum (weighted) matching

    Sepehr Assadi. A simple (1 -ϵ)-approximation semi-streaming algorithm for maximum (weighted) matching. In Merav Parter and Seth Pettie, editors,2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, V A, USA, January 8-10, 2024, pages 337–354. SIAM, 2024.doi:10. 1137/1.9781611977936.31

    work page 2024

  4. [4]

    On the Robust Communication Complexity of Bipar- tite Matching

    Sepehr Assadi and Soheil Behnezhad. On the Robust Communication Complexity of Bipar- tite Matching. In Mary Wootters and Laura Sanit` a, editors,Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48:17, Dagstuhl, ...

    work page doi:10.4230/lipics.approx/random.2021.48 2021

  5. [5]

    Semi-streaming bipartite matching in fewer passes and optimal space

    Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Semi-streaming bipartite matching in fewer passes and optimal space. In Joseph (Seffi) Naor and Niv Buchbinder, editors,Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, V A, USA, January 9 - 12, 2022, pages 627–669. SIAM...

    work page doi:10.1137/1.9781611977073.29 2022

  6. [6]

    Cliff Liu, and Robert E

    Sepehr Assadi, S. Cliff Liu, and Robert E. Tarjan. An auction algorithm for bipartite matching in streaming and massively parallel computation models. In Hung Viet Le and Valerie King, editors,4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 165–171. SIAM, 2021.doi:10.1137/1.9781611976496.18

    work page doi:10.1137/1.9781611976496.18 2021

  7. [7]

    Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. Exponentially faster mas- sively parallel maximal matching. In David Zuckerman, editor,60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1637–1649. IEEE Computer Society, 2019.doi:10.1109/FOCS.2019.00096. 10

    work page doi:10.1109/focs.2019.00096 2019

  8. [8]

    Improved bounds for matching in random-order streams.Theory Comput

    Aaron Bernstein. Improved bounds for matching in random-order streams.Theory Comput. Syst., 68(4):758–772, 2024. URL:https://doi.org/10.1007/s00224-023-10155-7,doi:10. 1007/S00224-023-10155-7

    work page doi:10.1007/s00224-023-10155-7 2024

Show all 17 references
  1. [9]

    Constructing large matchings via query access to a maximal matching oracle

    Lidiya Khalidah binti Khalil and Christian Konrad. Constructing large matchings via query access to a maximal matching oracle. In Nitin Saxena and Sunil Simon, editors,40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2...

    2020 doi

  2. [10]

    Bipartite matching in the semi-streaming model.Algorithmica, 63(1-2):490–508, 2012

    Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav. Bipartite matching in the semi-streaming model.Algorithmica, 63(1-2):490–508, 2012. URL:https://doi.org/10. 1007/s00453-011-9556-8,doi:10.1007/S00453-011-9556-8

    2012 doi

  3. [11]

    On graph problems in a semi-streaming model.Theor

    Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model.Theor. Comput. Sci., 348(2):207–216, December 2005. doi:10.1016/j.tcs.2005.09.013

    2005 doi

  4. [12]

    Karloff, Siddharth Suri, and Sergei Vassilvitskii

    Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapre- duce. In Moses Charikar, editor,Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 938–948. S...

    2010 doi

  5. [13]

    A simple augmentation method for matchings with applications to stream- ing algorithms

    Christian Konrad. A simple augmentation method for matchings with applications to stream- ing algorithms. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors,43rd In- ternational Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Au- gust 27-31, 20...

    2018 doi

  6. [14]

    Maximum matching in semi-streaming with few passes

    Christian Konrad, Fr´ ed´ eric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Anupam Gupta, Klaus Jansen, Jos´ e D. P. Rolim, and Rocco A. Servedio, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- ...

    2012 doi

  7. [15]

    Christian Konrad and Kheeran K. Naidu. On two-pass streaming algorithms for maximum bi- partite matching. In Mary Wootters and Laura Sanit` a, editors,Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2...

    2021 doi

  8. [16]

    Naidu, and Arun Steward

    Christian Konrad, Kheeran K. Naidu, and Arun Steward. Maximum matching via maximal match- ing queries. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kant´ e, editors,40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, ...

    2023 doi

  9. [17]

    Finding graph matchings in data streams

    Andrew McGregor. Finding graph matchings in data streams. In Chandra Chekuri, Klaus Jansen, Jos´ e D. P. Rolim, and Luca Trevisan, editors,Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algo- ...

    2005 doi

Pith tools

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