  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
$O\left(\frac{N\log^2(N)}{\log\left(Np\right)}\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(N\log(N))$.
