Content deleted Content added
Trivially, the simplex algorithm takes on average ''D'' steps for a cube. More generally, for the simplex algorithm, the expected number of steps is O(''D'') for linear-programming problems that are randomly drawn from the [[Euclidean sph |
Trivially, the simplex algorithm takes on average ''D'' steps for a cube. More generally, for the simplex algorithm, the expected number of steps is O(''D'') for linear-programming problems that are randomly drawn from the [[Euclidean met |
||
Line 1:
In [[optimization (mathematics)|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]] [[optimization (mathematics)|objective functions]]; 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 Dantzig|George B. Dantzig]], the criss-cross algorithm is not a [[time complexity|polynomial-time algorithm]] for linear programming. Both algorithms visit all 2<sup>''D''</sup> corners of a (perturbed) [[unit cube|cube]] in dimension ''D'', the [[Victor Klee|Klee]]-Minty cube.<ref>{{havtxt|Roos|1990}}</ref><ref name="KleeMinty"/> On average, the criss-cross algorithm visits only ''D'' corners, however.<ref name="FukudaTerlaky"/> Trivially, the simplex algorithm takes on average ''D'' steps for a cube. More generally, for the simplex algorithm, the expected number of steps is O(''D'') for linear-programming problems that are randomly drawn from the [[Euclidean metric|Euclidean]] [[unit sphere]], as proved by Borgwardt and by [[Stephen Smale|Smale]].
==Comparison with the simplex algorithm of Dantzig==
| |||