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

Q: What approximation guarantee does the ALT algorithm provide for bipartite maximum matching?

The ALT algorithm outputs a (1−ϵ)-approximation to maximum matching in bipartite graphs using O(ϵ^−1/2) maximal matchings.

Q: What simplification is proposed in the revisited algorithm analysis?

The freezing mechanism for repeatedly rematched vertices is shown to be unnecessary; removing it leaves ϵ as the sole parameter controlling the number of iterations/maximal matching computations.

Q: What does the paper contribute regarding hard instances?

It provides the first hard instance requiring Ω(ϵ^−1/2) iterations/maximal matching computations, demonstrated on a simple path graph with cyclic behavior that blocks fast progress.

Jul 16, 2026

Upload by Seraphina

Assadi, Liu, and Tarjan’s auction-based algorithm provides a (1−ϵ)-approximation to maximum bipartite matching using a sequence of O(ϵ^−1/2)-many maximal matchings, implementable in a multi-pass streaming model with O(ϵ^−1/2) passes. This work revisits the ALT algorithm with three contributions: removing an unnecessary freezing mechanism via simplification, giving an augmenting-paths style alternative analysis, and constructing the first hard instance showing Ω(ϵ^−1/2) iterations are required, including a cyclic slow-progress behavior on a simple path graph.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages11

Reading Time28 min

Abstract

Introduction

Matching and approximation background

Motivation from restricted computational models

ALT algorithm overview

Our results

arXiv :2607 .07439v2 [ cs .DS] 9 Jul 2026 On the Assadi–Liu–Tarjan Auction Algorithm for Bipartite Matching: Simplification, Alternative Analysis, and Hard Instance Christian Konrad∗ Kheeran K. Naidu† Archie Walton‡ Eric Wang§ Abstract Assadi, Liu, and Tarjan [SOSA’21] gave an auction algorithm that outputs a (1−ϵ)-approximation to Maximum Matching in bipartite graphs. Their algorithm computes a sequence of O( ϵ~~12~~ ) maximal matchings in subgraphs of the input graph and can be implemented in the multi-pass streaming setting with O ( ϵ~~12~~ ) 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: 1. Simplification. The ALT-algorithm is built upon a freezing mechanism where vertices on one side of the bipartition that have already been rematched Θ( ~~ 1~~ϵ) 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. With the freezing mechanism removed, the parameter ϵ now solely determines the total number of iterations/maximal matching computations, which provides the option of adaptively refining ϵ as the algorithm runs. 2. Alternative Analysis. We give an alternative analysis of the algorithm that is based on augmenting paths. Beyond the auction-perspective of the algorithm as established by Assadiet al., 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. 3. Hard Instance. We provide the first hard instance on which the algorithm requires Ω( ϵ~~12~~ ) iterations/maximal matching computations. The instance is a simple path graph, where we exhibit a cyclic behaviour that prevents fast progress. Hard instances for this algorithm therefore do not necessarily have to be dense. 1 Introduction A matching in a graph is a subset of vertex-disjoint edges. A matching is maximal if it cannot be enlarged by adding an edge outside of the matching to it, and a matching is maximum if it is of largest possible size. Then, the Maximum Matching problem (MM) consists of computing a maximum matching, and, for any 0 < α ≤ 1, an α-approximation algorithm to MM is an algorithm that outputsa matching of size at least α times the size of a maximum matching. Motivated by the fact that, in various restricted computational models, computing a maximal matching is an easy task, there has been growing interest in algorithms for MM approximation that are solely based on computing a sequence of maximal matchings in subgraphs of the input graph so that the union of these maximal matchings contains a non-trivial approximation to MM [9, 16] . For example, in the semi-streaming model of computation [11], where an algorithm performs multiple passes over ∗ [christian.konrad@bristol.ac.uk](christian.konrad@bristol.ac.uk), School of Computer Science, University of Bristol, UK. †[kheeran.naidu@gmail.com](kheeran.naidu@gmail.com), Qworky Research, London, UK. ‡[archie.walton@bristol.ac.uk](archie.walton@bristol.ac.uk), School of Computer Science, University of Bristol, UK. Supported by an EPSRC DTP studentship. § [erw015@ucsd.edu](erw015@ucsd.edu), University of California, San Diego, US. the edges of an n-vertex input graph while maintaining a memory of size O(n poly log n), a single pass is sufficient for computing a maximal matching. In the O (n)-memory massively parallel com

FAQs

What approximation guarantee does the ALT algorithm provide for bipartite maximum matching?

The ALT algorithm outputs a (1−ϵ)-approximation to maximum matching in bipartite graphs using O(ϵ^−1/2) maximal matchings.

What simplification is proposed in the revisited algorithm analysis?

The freezing mechanism for repeatedly rematched vertices is shown to be unnecessary; removing it leaves ϵ as the sole parameter controlling the number of iterations/maximal matching computations.

What does the paper contribute regarding hard instances?

It provides the first hard instance requiring Ω(ϵ^−1/2) iterations/maximal matching computations, demonstrated on a simple path graph with cyclic behavior that blocks fast progress.

Jul 16, 2026

Upload by Seraphina