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

Sophie Huiberts Yin Tat Lee Xinzhi Zhang

Published in: CoRR (2022)

Keyphrases

upper and lower bounds
simplex method
upper bound
linear programming
linear program
linear fractional
lower bound
worst case
lower and upper bounds
convergence rate
dnf formulas
computational complexity
primal dual
search algorithm
dynamic programming
markov random field