Logo

Mathematical Sciences Research Institute

Home » GFA Main Seminar: The minimum Euclidean norm point in a polytope: Wolfe's method is exponential

Seminar

GFA Main Seminar: The minimum Euclidean norm point in a polytope: Wolfe's method is exponential November 28, 2017 (03:30 PM PST - 04:30 PM PST)
Parent Program:
Location: MSRI: Simons Auditorium
Speaker(s) Luis Rademacher (University of California, Davis)
Description No Description
Video
No Video Uploaded
Abstract/Media

A long line of work in discrete geometry aims to find families of polyhedra where variants of the simplex method for linear programming take exponential time. This talk will be about another problem around this line. In 1974 Phillip Wolfe proposed a method to find the minimum Euclidean-norm point in a convex polyhedron. The complexity of Wolfe's method has remained unknown since he proposed it. 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.

No Notes/Supplements Uploaded No Video Files Uploaded