Content deleted Content added
→Summary: It is not a polynomial-time algorithm, however. Researchers have extended the criss-cross algorithm for many optimization-problems, including linear-fractional programming.<ref name="LF99Hyperbolic"/> The criss-cross algorithm can solve |
→Oriented matroids: MR0332165 (48 #10492) Klee, Victor; Minty, George J. How good is the simplex algorithm? Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), pp. |
||
Line 12:
|pages=417–479|doi=10.1017/CBO9780511586507|MR=1744046}}</ref>
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>
==Summary==
| |||