Criss-cross algorithm: Difference between revisions

Revision as of 22:33, 25 March 2011

Revision as of 22:38, 25 March 2011

Line 15:

The criss-cross algorithm is simpler than the simplex algorithm, because the criss-cross algorithm only has one-phase. Its pivoting rules are similar to the [[Bland's rule|least-index pivoting rule of Bland]].<ref name="Bland">

{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|number=2|month=May|year=1977|pages=103–107|url=http://www.jstor.org/stable/3689647|doi=10.1287/moor.2.2.103|jstor=3689647|MR=459599}}</ref> Bland's rule uses only [[sign function|sign]]s of coefficients rather than their [[real number|(real-number) order]] when deciding eligible pivots. Bland's rule selects an entering variables by comparing values of reduced costs, using the real-number ordering of the eligible pivots.<ref>R.G. name="Bland, New finite pivoting rules for the simplex method, ''Math. Oper. Res.'' 2 (1977) 103–107."/><pref>Bland's rule is also related to an earlier least-index rule, which was proposed by Katta&nbsp;G. Murty for the [[linear complementarity problem]], according to {{harvtxt|Fukuda|Namiki|1994}}.</ref> Unlike Bland's rule, the criss-cross algorithm is "purely combinatorial", selecting an entering variable and a leaving variable by considering only the signs of coefficients rather than their real-number ordering.<ref name="FukudaTerlaky"/><ref name="TerlakyZhang"/>

==Computational complexity: Worst and average cases==