Search Results

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(1/(ε²)) maximal matchings in subgraphs of the input graph and can be implemented in the multi-pass streaming setting with O(1/(ε²)) 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 Assadi et 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 Ω(1/(ε²)) 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.