Name
Title | ||
|---|---|---|
The minimum euclidean-norm point in 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. 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
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3188745.3188820 | STOC '18: Symposium on Theory of Computing
Los Angeles
CA
USA
June, 2018 |
Keywords | Field | DocType |
convex quadratic optimization,Wolfe's method,linear programming,strongly polynomial time algorithms,lower bounds | Discrete mathematics,Birkhoff polytope,Combinatorics,Euclidean distance,Simplex,Convex polytope,Linear programming,Wolfe duality,Vertex enumeration problem,Wolfe conditions,Mathematics | Conference |
Volume | ISSN | ISBN |
abs/1710.02608 | 0737-8017 | 978-1-4503-5559-9 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jesús A. De Loera | 1 | 357 | 42.24 |
| Jamie Haddock | 2 | 3 | 5.61 |
| Luis Rademacher | 3 | 269 | 21.60 |