Title: The Minimum Euclidean-Norm Point on a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential,
Abstract: 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.