Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method.

Sophie Huiberts Yin Tat Lee Xinzhi Zhang

Published in: STOC (2023)

Keyphrases

upper and lower bounds
simplex method
upper bound
linear program
linear programming
lower bound
linear fractional
worst case
convergence rate
lower and upper bounds
computational complexity
column generation
graph cuts
dnf formulas
support vector machine
primal dual
dynamic programming