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

Christian Konrad, Kheeran K. Naidu, Archie Walton +1

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(…