A Lower Bound on the Expected Cost of an Optimal Assignment

We propose a dual heuristic for the assignment problem. We analyze this heuristic when the costs are independently and uniformly distributed between 0 and 1. As a result, we derive a lower bound on the expected cost of an optimal assignment, namely we show that it exceeds α − o(1), where α > 1.441.