Content deleted Content added
→Computational complexity: Worst and average cases: put details about Simplex in footnote |
|||
Line 25:
However, like the simplex algorithm of Dantzig, the criss-cross algorithm is ''not'' a polynomial-time algorithm for linear programming. Terlaky's criss-cross algorithm visits all the 2<sup>''D''</sup> corners of a (perturbed) cube in dimension ''D'', according to a paper of Roos; Roos's paper modifies the [[Victor Klee|Klee]]–Minty construction of a [[unit cube|cube]] on which the simplex algorithm takes 2<sup>''D''</sup> steps).<ref name="FukudaTerlaky"/><ref name="Roos"/><ref name="KleeMinty">{{cite book|title=Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|___location=New York-London|year=1972|MR=332165|last1=Klee|first1=Victor|authorlink1=Victor Klee|last2=Minty|first2= George J.|authorlink2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175|ref=harv}}</ref> Like the simplex algorithm, the criss-cross algorithm visits all 8 corners of the three-dimensional cube in the worst case.
When it is initialized at a random corner of the cube, the criss-cross algorithm visits only ''D'' additional corners, however, according to a 1994 paper by Fukuda and Namiki.<ref name="FukudaNamiki" >{{harvtxt|Fukuda|Namiki|1994|p=367}}</ref><ref name="FTNamiki" >{{harvtxt|Fukuda|Terlaky|1997|p=385}}</ref> Trivially, the simplex algorithm takes on average ''D'' steps for a cube.
==Variants==
| |||