The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential

DOI10.1145/3188745.3188820zbMath1428.90117arXiv1710.02608OpenAlexW2763440175MaRDI QIDQ5230318

Jamie Haddock, Jesús A. De Loera, Luis Rademacher

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.02608

zbMATH Keywords

linear programminglower boundsconvex quadratic optimizationWolfe's methodstrongly polynomial time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Computational aspects related to convexity (52B55) Quadratic programming (90C20)

Related Items (1)

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

This page was built for publication: The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential