Technical Note—A Polynomial Simplex Method for the Assignment Problem

Operations Research · 1983 · Volume 31 · Issue 3

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.

Keywords

484 polynomial simplex algorithm for the assignment problem

Enable JavaScript for citation tools and additional paper interactions.