Average Case Analysis of a Heuristic for the Assignment Problem

Abstract
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(n2) 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 thus heuristic is bounded above by 3 + O(n−α), for some posrtive constant a.

This publication has 0 references indexed in Scilit: