# Expected time complexity of the auction algorithm and the push relabel algorithm for maximal bipartite matching on random graphs

arXiv: https://arxiv.org/abs/1401.0119 · HTML: https://mlsanity.com/paper/1401.0119/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2013.

## Built on by (most cited first, 2 of 2)

- [New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning](https://mlsanity.com/paper/2207.09588/) (2022)
- [Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits](https://mlsanity.com/paper/2306.04498/) (2023)

## Abstract (arXiv)

In this paper we analyze the expected time complexity of the auction algorithm for the matching problem on random bipartite graphs. We prove that the expected time complexity of the auction algorithm for bipartite matching is Oleft(fracNlog2(N)logleft(Npright)right) on sequential machines. This is equivalent to other augmenting path algorithms such as the HK algorithm. Furthermore, we show that the algorithm can be implemented on parallel machines with O(log(N)) processors and shared memory with an expected time complexity of O(Nlog(N)).