2 ms·
> Simplex algorithm should never work given its exponential worst case performance. Note that it has been proven however that if you slightly perturbate the in
by SkiFire13 2y ago
> Simplex algorithm should never work given its exponential worst case performance.
Note that it has been proven however that if you slightly perturbate the inputs then the expected complexity becomes polynomial, meaning the inputs for which it's exponential are actually just pathological cases and it is polynomial in practice.
- FooBarBizBazz 2y agoMan, there was a lot of obtuse argument to wade through to get to this post. This is an interesting fact. Apparently this is the source? https://arxiv.org/abs/cs/0111050 https://arxiv.org/abs/cs/0111050