Is it proven, yet, that the simplex algorithm has a smoothed polynomial complexity? Last thing I remember, there were still looking for a variant of the simplex that had that property. (The ellipsoid method and inner point methods are already proven to be polynomial, so we do know that linear programming is polynomial.)
> Its worth noting that smoothed analysis only really makes sense on algorithms where perturbing the input only changes the answer a little bit, so you need some sort of "numerical stability" style property for the underlying algorithm one way or another.
Aren't there discrete alternatives available?