Criss-cross algorithm: Difference between revisions

Revision as of 20:21, 27 March 2011

Revision as of 20:23, 27 March 2011

Line 3:

[[Image :Unitcube.svg|thumb|right|alt=A three-dimensional cube|The criss-cross algorithm visits all 8 corners of the [[Klee–Minty cube]] in the worst case. It visits 3 additional corners on average. The Klee–Minty cube is a perturbation of the cube shown here.]]

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><ref name="Bibl" >{{cite journal|first=I.&nbsp;M.|last=Stancu-Minasian|title=A sixth bibliography of fractional programming|journal=Optimization|volume=55|number=4|month=August|

|url=http://www.informaworld.com/10.1080/02331930600819613| year=2006|pages=405–428|doi=10.1080/02331930600819613|'''MR=2258634'''}}</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&nbsp;2^''D''&nbsp;corners of a (perturbed) [[unit cube|cube]] in dimension&nbsp;''D'', the [[Klee–Minty cube]] (after [[Victor Klee]] and [[George J. Minty]]), in the [[worst-case complexity|worst case]].<ref name="Roos" >{{harvtxt|Roos|1990}}</ref><ref name="KleeMinty"/> However, when it is started at a random corner, the criss-cross algorithm [[Average-case complexity|on&nbsp;average]] visits only&nbsp;''D'' additional corners.<ref name="FTNamiki"/><ref name="FukudaNamiki"/><ref name="Borgwardt">The simplex algorithm takes on average&nbsp;''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|___location=Berlin|year=1987|pages=xii+268|isbn=3-540-17096-0|MR=868467|ref=harv}}</ref> Thus, for the three-dimensional cube, the algorithm visits all&nbsp;8 corners in the worst case and exactly&nbsp;3 additional corners on&nbsp;average.