Editing Linear programming (section)

==== Criss-cross algorithm ====
Like the simplex algorithm of Dantzig, the [[criss-cross algorithm]] is a basis-exchange algorithm that pivots between bases. However, the criss-cross algorithm need not maintain feasibility, but can pivot rather from a feasible basis to an infeasible basis. The criss-cross algorithm does not have [[time complexity|polynomial time-complexity]] for linear programming. Both algorithms visit all&nbsp;2<sup>''D''</sup> corners of a (perturbed) [[unit cube|cube]] in dimension&nbsp;''D'', the [[Klee–Minty cube]], in the [[worst-case complexity|worst case]].<ref name="FukudaTerlaky">{{cite journal|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor=Thomas M. Liebling |editor2=Dominique de Werra|year=1997|doi=10.1007/BF02614325|mr=1464775|citeseerx=10.1.1.36.9373|s2cid=2794181}}</ref><ref name="Roos">{{cite journal|last=Roos|first=C.|title=An exponential example for Terlaky's pivoting rule for the criss-cross simplex method|journal=Mathematical Programming|volume=46|year=1990|series=Series A|doi=10.1007/BF01585729|mr=1045573 |issue=1|pages=79–84|s2cid=33463483}}</ref>