3 ms·
This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.
by Tainnor 6y ago
This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.
- eru 6y agoI just searched for 'polynomial time simp lex algorithm' and found things like eg https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm https://cstheory.stackexchange.com/questions/2373/complexity... which references https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc....
- Tainnor 6y agothanks, it seems to be quite complex though, as far as I understand it's still "only" an expected polynomial algorithm given some assumptions about the input, and not a truly worst-case polynomial algorithm - as opposed to e.g. the ellipsoid method which is actually worst-case polynomial.
- eru 6y agoAs far as I understand it's runs in expected polynomial time regardless of input. No assumptions on the input necessary. The expectation is over the choice of random bits created while running the algorithm.