A polynomial-time linear programming solver based on the perceptron algorithm

John Dunagan
Microsoft Research

Abstract: 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. This is joint work with Santosh Vempala (MIT).