3 ms·
1) the linked paper PROVES simplex has polynomial smoothed complexity. So yes, this paper proves it. Interior points etc have polynomial worst case complexity,
by carterschonwald 13y ago
1) the linked paper PROVES simplex has polynomial smoothed complexity. So yes, this paper proves it.
Interior points etc have polynomial worst case complexity, which is a different notion ;)
2) yes, theres discrete alternatives, but they're not as problem agnostic as "numerical stability"
- eru 13y agoI didn't read the paper, yet. I was relying on my failing memory of university courses. OK, so I guess the open challenge, I remember, was to do what everyone knows should be possible: come up with a version of simplex that chooses clever enough to get polynomial worst case complexity. (Do you know if any probabilistic variants are in the running?) Yes, numerical stability is great as a measure.
- carterschonwald 13y agoyes, Dan has a randomized simplex with polynomial time. I don't remember the details, but the paper (not paywalled) can be found here http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.p... It was published around 2009 or so, iirc.