A Lower Bound on the Expected Cost of an Optimal Assignment
- 1 May 1993
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 18 (2) , 267-274
- https://doi.org/10.1287/moor.18.2.267
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: