A Polynomial-time Rescaling Algorithm for Solving Linear Programs

John Dunagan; Santosh Vempala

A Polynomial-time Rescaling Algorithm for Solving Linear Programs

John Dunagan ,
Santosh Vempala

MSR-TR-2003-09 | January 2003

Note: This report was previously assigned the number MSR-TR-2002-92. Please change any citations to reflect the new report number.

Publication

Download BibTex

We show that the perceptron algorithm along with periodic rescaling solves linear programs in polynomial time. The algorithm requires no matrix inversions and no barrier functions.