Content deleted Content added
dab Namiki footnote |
→Properties: 1994 paper by Fukuda and Namiki.<ref name="FTNamiki" >{{harvtxt|Fukuda|Terlaky|1997|p=385}}</ref> |
||
Line 10:
==Properties==
Like the simplex algorithm of Dantzig, the criss-cross algorithm is not a [[time complexity|polynomial-time algorithm]] for linear programming. The original criss-cross algorithm of Terlaky visits all the 2<sup>''D''</sup> corners of a (perturbed) cube in dimension ''D'', according to a paper of Roos; Roos's paper modifies the [[Victor Klee|Klee]]–Minty construction of a [[unit cube|cube]] on which the simplex algorithm takes 2<sup>''D''</sup> steps).<ref name="FukudaTerlaky"/><ref name="Roos"/><ref name="KleeMinty">{{cite book|title=Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|___location=New York-London|year=1972|MR=332165|last1=Klee|first1=Victor|authorlink1=Victor Klee|last2=Minty|first2= George J.|authorlink2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175|ref=harv}}</ref> On average, the criss-cross algorithm visits only ''D'' corners, however, according to a 1994 paper by Fukuda and Namiki.<ref name="FTNamiki" >{{harvtxt|Fukuda|Terlaky|1997|p=385}}</ref> Trivially, the simplex algorithm takes on average ''D'' steps for a cube. More generally, for the simplex algorithm, the expected number of steps is proportional to ''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]].
The criss-cross algorithm was published independently by [[Tamás Terlaky]]<ref> {{harvtxt|Terlaky|1985}} and {{harvtxt|Terlaky|1987}} </ref> and by Zhe-Min Wang;<ref name="Wang" >{{harvtxt|Wang|1987}} </ref> related algorithms appeared in unpublished reports by other authors. The criss-cross algorithm is often studied using the theory of [[oriented matroid]]s (OMs), which is a [[combinatorics|combinatorial]] abstraction of linear-optimization theory.<ref>The theory of [[oriented matroid]]s was initiated by [[R. Tyrrell Rockafellar]] to describe the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm; Rockafellar was inspired by [[Albert W. Tucker]] studies of such sign patterns in "Tucker tableaux". {{harv|Rockafellar|1969}}</ref> Indeed, Bland's pivoting rule was based on his previous papers on oriented matroid theory. Much literature on the criss-cross algorithm concerns oriented matroids. Historically, OM algorithms for [[quadratic programming|quadratic-programming problems]] and [[linear complementarity problem|linear-complementarity problem]]s had been published by [[Michael J. Todd (mathematician)|Michael J. Todd]] before Terlaky and Wang published their criss-cross algorithms.<ref name="Todd" > {{cite journal|last=Todd|first=Michael J.|authorlink=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series B|volume=39|year=1985|number=2|pages=105–133|MR=811116|doi=10.1016/0095-8956(85)90042-5|url=http://dx.doi.org/10.1016/0095-8956(85)90042-5}} </ref> However, Todd's pivoting-rule cycles on nonrealizable oriented matroids (and only on nonrealizable oriented matroids). Such cycling does not stump the OM criss-cross algorithms of Terlaky and Wang, however. There are oriented-matroid variants of the criss-cross algorithm for linear programming, for quadratic programming, and for the linear-complementarity problem.<ref name="FukudaTerlaky"/><ref name="OMBook" >{{cite book|last=Björner|first=Anders|last2=Las Vergnas|first2=Michel|last3=Sturmfels|first3=Bernd|authorlink3=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter|authorlink5=Günter M. Ziegler|title=Oriented Matroids|chapter=10 Linear programming|publisher=Cambridge University Press|year=1999|isbn=9780521777506|url=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507|
| |||