"David X. Cohen: Graduated magna cum laude with a bachelor's degree in physics from Harvard University in 1988. He received his master's degree in computer science from UC Berkeley in 1992. He published the following article with Manuel Blum: On the Problem of Sorting Burnt Pancakes. Discrete Appl. Math. 61 (1995), no. 2, 105--120."
Here is the abstract:
The "pancake problem" is a well-known open combinatorial problem that recently has been shown to have applications to parallel processing. Given a stack of n pancakes in arbitrary order, all of different sizes, the goal is to sort them into the size-ordered configuration having the largest pancake on the bottom and the smallest on top. The allowed sorting operation is a "spatula flip", in which a spatula is inserted beneath any pancake, and all pancakes above the spatula are lifted and replaced in reverse order. The problem is to bound f(n), the minimum number of flips required in the worst case to sort a stack of n pancakes. Equivalently, we seek bounds on the number of prefix reversals necessary to sort a list of n elements. Bounds of 17n/16 and (5n + 5)/3 were shown by Gates and Papadimitriou in 1979. In this paper, we consider a traditional variation of the problem in which the pancakes are two sided (one side is "burnt"), and must be sorted to the size-ordered configuration in which every pancake has its burnt side down. Let g(n) be the number of flips required to sort n "burnt pancakes". We find that 3n/2 less-than-or-equals, slant g(n) less-than-or-equals, slant 2n 2, where the upper bound holds for n gt-or-equal, slanted 10. We consider the conjecture that the most difficult case for sorting n burnt pancakes is In, the configuration having the pancakes in proper size order, but in which each individual pancake is upside down. We present an algorithm for sorting In in 23n/14 + c flips, where c is a small constant, thereby establishing a bound of g(n) less-than-or-equals, slant 23n/14 + c under the conjecture. Furthermore, the longstanding upper bound of f(n) is also improved to 23n/14 + c under the conjecture.
Remember that Betamax failed, despite slightly better technology, because Sony kept it proprietary. To play or record Betamax tapes, until the URL: the looks of the Pvery end you had to buy Sony hardware. That let the open VHS market develop commodity recorders and players that enormously outnumbered Sony and undercut it on price.
The market has room for many levels, from high-end to junk. Sony limited itself to good-to-excellent hardware, while most buyers wanted mid-to-low end. Sony got buried. True, it was mostly in manure, but the important thing is that it got buried.
Isn't this the exact same situation that Apple was in with its iPod/iTunes? Somehow, the closed format is killing all the competition (including those dirt cheap Chinese players).
All Sony has to do is make it's players look "hip" and the BluRay format is in the bag.
Of course, judging from the looks of the PS3, everything is still in the air.
Slashdot Mirror
"David X. Cohen: Graduated magna cum laude with a bachelor's degree in physics from Harvard University in 1988. He received his master's degree in computer science from UC Berkeley in 1992. He published the following article with Manuel Blum: On the Problem of Sorting Burnt Pancakes. Discrete Appl. Math. 61 (1995), no. 2, 105--120."
Here is the abstract:
The "pancake problem" is a well-known open combinatorial problem that recently has been shown to have applications to parallel processing. Given a stack of n pancakes in arbitrary order, all of different sizes, the goal is to sort them into the size-ordered configuration having the largest pancake on the bottom and the smallest on top. The allowed sorting operation is a "spatula flip", in which a spatula is inserted beneath any pancake, and all pancakes above the spatula are lifted and replaced in reverse order. The problem is to bound f(n), the minimum number of flips required in the worst case to sort a stack of n pancakes. Equivalently, we seek bounds on the number of prefix reversals necessary to sort a list of n elements. Bounds of 17n/16 and (5n + 5)/3 were shown by Gates and Papadimitriou in 1979. In this paper, we consider a traditional variation of the problem in which the pancakes are two sided (one side is "burnt"), and must be sorted to the size-ordered configuration in which every pancake has its burnt side down. Let g(n) be the number of flips required to sort n "burnt pancakes". We find that 3n/2 less-than-or-equals, slant g(n) less-than-or-equals, slant 2n 2, where the upper bound holds for n gt-or-equal, slanted 10. We consider the conjecture that the most difficult case for sorting n burnt pancakes is In, the configuration having the pancakes in proper size order, but in which each individual pancake is upside down. We present an algorithm for sorting In in 23n/14 + c flips, where c is a small constant, thereby establishing a bound of g(n) less-than-or-equals, slant 23n/14 + c under the conjecture. Furthermore, the longstanding upper bound of f(n) is also improved to 23n/14 + c under the conjecture.