Interior Point Methods Solve Random LPs in polylog(n) iterationsResearch Paper
Interior point methods (IPMs) and the simplex method are the standard tools for solving linear programs in practice. Path-following IPMs carry a worst-case guarantee of iterations, proved in 1988–1989 (Renegar; Kojima–Mizuno–Yoshise; Monteiro–Adler) and never improved since. Production codes, however, solve programs with…