Technical Note—A Polynomial Simplex Method for the Assignment Problem

Abstract

We present a polynomial primal simplex algorithm for the assignment problem. For n × n assignment problem with integer cost coefficients, the algorithm generates at most n 3 ln ▵ bases prior to reach the optimal basis, where ▵ is the difference in objective value between an initial extreme point and the optimal extreme point.