Rebecca Hoberg; A Polynomial-time LP Algorithm based on Multiplicative Weights

May 10, 2016, 4pm
GUG 204
Rebecca Hoberg, Department of Mathematics, UW

Abstract:  The multiplicative weights update method is a meta-algorithm with varied applications. As Arora, Hazan, and Kale show, applying this method with nonnegative weights on constraints yields an algorithm for linear programming. However, in polynomial time this approach only computes an approximate solution. In this talk, I will show how we can improve this to an exact polynomial-time algorithm. We do this by introducing a rescaling step similar to that used by Dunagan and Vempala for the perceptron algorithm. This is joint work with Thomas Rothvoss and Jon Swenson.