Average case analysis of a heuristic for the assignment problem

The authors main contribution is an O(nlogn) algorithm that determines with high probability a perfect matching in a random 2-out bipartite graph. They also show that this algorithm runs in O(n) expected time. This algorithm can be used as a subroutine in an O(n²) heuristic for the assignment problem. When the weights in the assignment problem are independently and uniformly distributed in the interval [0,1], the authors prove that the expected weight of the assignment returned by this heuristic is bounded above by 3+O(n’-^a), for some positive constant a.