Editing Pancake sorting (section)

==History==
The pancake sorting problem was first posed by [[Jacob E. Goodman]], writing under the pseudonym "Harry Dweighter" ("harried waiter").<ref>{{citation
|first1=Harry|last1=Dweighter
|title= Elementary Problem E2569
|journal = Amer. Math. Monthly
|volume= 82
|issue=10
|pages=1009–1010
|year=1975
|doi=10.2307/2318260|jstor=2318260
}}
</ref>

Although seen more often as an educational device, pancake sorting also appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors.<ref>{{Cite journal| last1 = Gargano | first1 = L.
 | last2 = Vaccaro | first2 = U.
 | last3 = Vozella | first3 = A.
 | doi = 10.1016/0020-0190(93)90043-9
 | issue = 6
 | journal = Information Processing Letters
 | mr = 1216942
 | pages = 315–320
 | title = Fault tolerant routing in the star and pancake interconnection networks
 | volume = 45
 | year = 1993| citeseerx = 10.1.1.35.9056
 }}.</ref><ref>{{Cite book| last1 = Kaneko | first1 = K.
 | last2 = Peng | first2 = S.
 | contribution = Disjoint paths routing in pancake graphs
 | doi = 10.1109/PDCAT.2006.56
 | pages = 254–259
 | title = Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06)
 | year = 2006| isbn = 978-0-7695-2736-9 | s2cid = 18777751
 }}.</ref>

The problem is notable as the topic of the only well-known mathematics paper by [[Microsoft]] founder [[Bill Gates]] (as William Gates), entitled "Bounds for Sorting by Prefix Reversal" and co-authored with [[Christos Papadimitriou]]. Published in 1979, it describes an efficient algorithm for pancake sorting.<ref name=Gates1979>{{cite journal |title=Bounds for Sorting by Prefix Reversal |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=27 |pages=47–57 |year=1979 |doi=10.1016/0012-365X(79)90068-2 |last1=Gates |first1=W. |last2=Papadimitriou |first2=C. |author-link1=Bill Gates |author-link2=Christos Papadimitriou |doi-access=free }}</ref> In addition, the most notable paper published by ''[[Futurama]]'' co-creator [[David X. Cohen]] (as David S. Cohen), co-authored with [[Manuel Blum]], concerned the burnt pancake problem.<ref>{{Cite journal|last1=Cohen|first1=D.S. |last2= Blum|first2=M.|doi=10.1016/0166-218X(94)00009-3|title=On the problem of sorting burnt pancakes|year=1995|journal=Discrete Applied Mathematics|volume=61|issue=2|pages=105|author-link1=David X. Cohen|author-link2=Manuel Blum|doi-access=free}}</ref>

The connected problems of signed sorting by reversals and sorting by reversals were also studied more recently. Whereas efficient exact algorithms have been found for the signed sorting by reversals,<ref>{{cite journal|last1=Kaplan|first1=H.|last2=Shamir|first2=R.|author3-link=Robert Tarjan|last3=Tarjan|first3=R.E.|title=Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals|journal=Proc. 8th ACM-SIAM SODA|date=1997|pages=178–87}}</ref> the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor,<ref>{{cite journal|last1=Berman|first1=P.|author2-link=Marek Karpinski|last2=Karpinski|first2=M.|url=http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/1998/85193-CS.ps.gz|title=On Some Tighter Inapproximability Results.|journal=Proc. 26th ICALP (1999) |series=Lecture Notes in Computer Science |volume=1644|year=1999|pages=200–09}}</ref> and also proven to be approximable in polynomial time to within the approximation factor 1.375.<ref>{{cite journal|last1=Berman|first1=P.|author2-link=Marek Karpinski|last2=Karpinski|first2=M.|last3=Hannenhalli|first3=S.|url=http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2001/85228-CS.ps.gz|title=1.375-Approximation Algorithms for Sorting by Reversals.|journal=Proc. 10th ESA (2002) |series=Lecture Notes in Computer Science |volume=2461|pages=200–10|year=2002}}</ref>