Abstract - IPAM

Abstract

A polynomial relaxation-type algorithm for linear programming

Sergei Chubanov

Universität-GHS Siegen

We propose a strongly polynomial relaxation-type algorithm which either finds a solution of a linear system or decides that the system has no 0,1-solutions. If the system is feasible and the bounds on variables are tight, the algorithm always finds a solution. We show that the algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming.
No video available
Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?