3 ms·
This article, unless I'm missing something, doesn't actually explain why the algorithm works so well. It just gives the back story that led to the journal paper
by acbart 4y ago
This article, unless I'm missing something, doesn't actually explain why the algorithm works so well. It just gives the back story that led to the journal paper explaining it.
- npalli 4y agoThe article discusses how the two mathematicians (Spielman and Teng) came up with Smoothed Analysis for Algorithms (as opposed to Worst case) which gives insight into why Simplex works well. We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity https://arxiv.org/abs/cs/0111050 https://arxiv.org/abs/cs/0111050 The two authors won the Godel prize in 2008 for this work.
- deleted 4y ago[deleted]
- adhesive_wombat 4y agoIt doesn't even seem to say what the algorithm does, just that it's very commonly used. I had completely forgotten I used to solve by hand at school until I looked it up: the article didn't jog that memory at all.