Slashdot Mirror
The Secret of the Simplex Algorithm Discovered
prostoalex writes "While the Simplex algorithm is considered to be one of the most widely used algorithms in complex networks, the reason for its efficiency has been so far not too clear. Daniel Spielman and Shanghua Teng discovered the secret of why the Simplex algorithm works so well by introducing imprecision into the worst-case scenario analysis. Their article will be published in Journal of ACM, although MIT Technology Review at the aforementioned link quotes Spielman expressing his doubts whether anyone will be able to make it through 80-page document filled with equations and formal explanations of the method."
Euler was wrong?? I don't think that argument holds water. While 80 pages is long for a proof it looks like more of a philosophical diatribe than anything else.
One of the more interesting pieces of 'lore' about the inventor of the simplex method, George Dantzig, is that while in graduate school he showed up late for class and wrote down the pair of problems on the board, thinking they were an assignment.
He struggled for a while, and finally turned his results into to the professor. However, the problems had been two famous unsolved problems in the field, and Dantzig had effectively solved them.
While perhaps embellished (and not the only example of students solving 'unsolved' problems), it has become a parable for showing the power of unprejudiced thought. Occasionally it is mis-stated that he invented the simplex method to solve these problems, when in fact, he did that a couple of years afterwards.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
The simplex method is widely used in Operations Research and many classic 'computing' problems. For example, IIRC the "Shortest Route" problem is managed (solved is too strong a word, for reasons explained in the previous post). For instance, if your business has three warehouses, 20 trucks and 10 major customers, how do you determine the cheapest way to supply all the customers with the goods they need? The 'best result' often seems counterintuitive.
:O)
It's also used by the airlines to figure out how to schedule planes. There are uses in physics, social sciences, etc. I don't know any offhand, but I wouldn't be surprised if at one time it was used to assist in scheduling computing resources. It's also widely used in complex pricing models.
It's also a way to decide, given 10 women and 10 men (or any number), which ones are most likely to get along with each other based on their preferences and characteristics.
It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
From the paper:
Another way of thinking about smoothed complexity is to observe that if an algorithm has low smoothed complexity, then one must be unlucky to choose an input instance on which it performs poorly.
If my first scan of paper yielded anything worth reporting it's the idea that even though a worst case may take exponential time to solve, there is always a neighborhood around the worst case that can be solved in polynomial time and has (almost) the same solution. In other words you can always find a good enough solution quickly.
BTW, those of you who described the idea as largely philosophical were wrong! The paper is mathematically rigorous. It uses the 80 pages to develop the theorems necessary to prove the idea.
Another famous one in the computer science field, was Huffman coding. As a graduate student, David Huffman (and the class) were early on given the choice of taking the final or doing a report on one of a few problems the professor outlined. The problems seemed straightforward, but the professor (Robert Fano of M.I.T., I believe) had assigned them because were unsolved problems; the idea being that the student would do the research, figure out that they were hard problems, and give a report on what research had been done to try and solve them.
Huffman didn't do the research, just spent weeks thinking about it, and eventually, when he had decided to give up and study for the test, the answer came to him and he realized the solution was really quite trivial (the famous "greedy algorithm" for constructing optimal minimum redundancy codes).
On the day of presentation, Huffman strode to the board, described the problem to the class, and totally unaware that it had not previously been solved (despite much effort), wrote the simple algorithm for constructing the codes on the chalkboard.
The professor was, understandably, stunned.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
It's a mathematical term. In 2 dimensions, a simplex is a triangle (3 points connected in all possible ways - ie. by 3 lines). In 3 dimensions, a simplex is a tetrahedron (4 points connected in all possible ways - ie. by 6 lines). In 10 dimensions, a simplex is 11 points connected in all possible ways - ie. by 11x10/2 lines.
Does this mean we should randomly perturb our quicksort inputs to help them sort in polynomial time? That intuitively makes sense. For a worst case quicksort input (typically a reverse sorted input), you could randomly permute the values to makes it O(N log N) rather than O(N). Cool.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward