Content deleted Content added
→Properties: ce |
→Properties: remove OM see also |
||
Line 8:
==Properties==
Like the simplex algorithm of Dantzig, the criss-cross algorithm is not a [[polynomial-time algorithm]] for linear programming. The original criss-cross algorithm of Terlaky visits all the 2<sup>''D''</sup> corners of a (perturbed) cube in dimension ''D'', according to a paper of Roos (which modifies the Klee-Minty construction of a cube on which the simplex algorithm takes 2<sup>''D''</sup> steps.<ref name="FukudaTerlaky"/><ref>{{harvtxt|Roos|1990}}</ref><ref>{{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>
| |||