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).