Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Exit Seminar: The Minimum Euclidean-Norm Point on a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential

Special Events

Speaker: Jamie Haddock, UC Davis
Location: 1147 MSB
Start time: Thu, May 17 2018, 12:10PM

The complexity of Philip Wolfe's method for the minimum Euclidean-norm point problem over a convex polytope has remained unknown since he proposed the method in 1974. The method is important because it is used as a subroutine for one of the most practical algorithms for submodular function minimization. We present the first example that Wolfe's method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in strongly-polynomial time to the minimum norm point problem over a simplex. I will also summarize the rest of my thesis which is on a related but separate subject.

Reception to follow.