No self-concordant barrier interior point method is strongly polynomial.
Xavier AllamigeonStéphane GaubertNicolas VandamePublished in: STOC (2022)
Keyphrases
- strongly polynomial
- interior point methods
- linear programming
- linear program
- primal dual
- semidefinite programming
- optimal solution
- inequality constraints
- minimum cost flow
- interior point algorithm
- feasible solution
- convex optimization
- np hard
- quadratic programming
- dynamic programming
- objective function
- denoising
- shortest path algorithm
- sufficient conditions
- pairwise