Average Case Analysis of a Heuristic for the Assignment Problem

Our main contribution is an O(n log n) algorithm that determines with high probability a perfect matching in a random 2-out bipartite graph. We also show that this algorithm runs in O(n) expected time. This algorithm can be used as a subroutine in an O(nsup2/sup) heuristic for the assignment problem. When the weights in the assignment problem are independently and uniformly distributed in the interval [0, 1], we prove that the expected weight of the assignment returned by this heuristic is bounded above by tex-math$3+O(n^{-a})$/tex-math, for some positive constant a.