4 ms·
> should never work given its exponential worst case performance This is again not true. We know why it works well. See the paper "Smoothed analysis of algori
by JohnKemeny 2y ago
> should never work given its exponential worst case performance
This is again not true. We know why it works well. See the paper
"Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time"
by Spielmann and Teng.
- whatever1 2y agoWe started understanding of why it works so well like 30 years after its first implementation (in the 1950's)? The paper you mention is written in the 2000s while the Simplex dominated the field from at least the 70's. Meanwhile the GP would have discarded the simplex algorithm due to its worst case performance.