A polynomial relaxation-type algorithm for linear programming

Sergei Chubanov
Universität-GHS Siegen
Faculty of Economics

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.

Presentation (PowerPoint File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?