Content deleted Content added
m →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 (pe |
Like the simplex algorithm of George B. Dantzig, the criss-cross algorithm is not a polynomial-time algorithm for linear programming. Both algorithms visit all 2<sup>''D''</sup> corners of a (perturbed) cube in dimension '' |
||
Line 1:
In [[mathematical optimization]], the '''criss-cross algorithm''' denotes a family of [[algorithm]]s for [[linear programming]]. Variants of the criss-cross algorithm also solve more general problems with [[linear programming|linear inequality constraints]] and [[nonlinear programming|nonlinear]] [[objective function]]s; there are criss-cross algorithms for [[linear-fractional programming]] problems,<ref name="LF99Hyperbolic">{{harvtxt|Illés|Szirmai|Terlaky|1999}}</ref> [[quadratic programming|quadratic-programming]] problems, and [[linear complementarity problem]]s.<ref name="FukudaTerlaky" > {{harvtxt|Fukuda|Terlaky|1997}} </ref>
Like the [[simplex algorithm]] of [[George B. Dantzig]], the criss-cross algorithm is not a [[polynomial-time algorithm]] for linear programming. Both algorithms visit all 2<sup>''D''</sup> corners of a (perturbed) cube in dimension ''D'', the [[Victor Klee|Klee]]-Minty cube.<ref name="FukudaTerlaky"/><ref name="KleeMinty"/>
==Comparison with the simplex algorithm of Dantzig==
| |||