New Auction Algorithms for the Assignment Problem and Extensions

Dimitri Bertsekas

We consider the classical linear assignment problem, and we introduce new auction algorithms for its optimal and suboptimal solution. The algorithms are founded on duality theory,…