Technical Note—A Polynomial Simplex Method for the Assignment Problem

1 June 1983

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 31 (3) , 595-600
https://doi.org/10.1287/opre.31.3.595

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³ 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

SIMPLEX
ASSIGNMENT
EXTREME POINT
SUP
OPTIMAL BASIS
POLYNOMIAL PRIMAL
INTEGER COST

This publication has 0 references indexed in Scilit: