Efficient dual simplex algorithms for the assignment problem

Efficient algorithms based upon Balinski's signature method are described for solving then × n assignment problem. These algorithms are special variants of the dual simplex method and are shown to have computational bounds of O(n ³). Variants for solving sparse assignment problems withm arcs that require O(m) space and O(mn + n ² logn) time in the worst case are also presented.This research was supported in part by the National Science Foundation under Grant No. MCS-8006064 and by the Army Research Office under Contracts No. DAAG 29-82-K0163 and DAAG 29-83-K0106