Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method.

Roman Vershynin

Published in: SIAM J. Comput. (2009)

Keyphrases

simplex method
linear programming
linear program
linear fractional
primal dual
convergence rate
column generation
worst case
computational complexity
linear programming problems
objective function
approximation algorithms
interior point algorithm
convex hull
randomly generated
np hard
search algorithm