Content deleted Content added
Citation bot (talk | contribs) Add: s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed access-date with no URL. Removed parameters. Some additions/deletions were parameter name changes. Upgrade ISBN10 to ISBN13. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform |
|||
Line 32:
However, like the simplex algorithm of Dantzig, the criss-cross algorithm is ''not'' a polynomial-time algorithm for linear programming. Terlaky's criss-cross algorithm 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|author-link1=Victor Klee|last2=Minty|first2= George J.|author-link2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175}}</ref> Like the simplex algorithm, the criss-cross algorithm visits all 8 corners of the three-dimensional cube in the worst case.
When it is initialized at a random corner of the cube, the criss-cross algorithm visits only ''D'' additional corners, however, according to a 1994 paper by [[Komei Fukuda|Fukuda]] and Namiki.<ref name="FTNamiki" >{{harvtxt|Fukuda|Terlaky|1997|p=385}}</ref><ref name="FukudaNamiki" >{{harvtxt|Fukuda|Namiki|1994|p=367}}</ref> Trivially, the simplex algorithm takes on average ''D'' steps for a cube.<ref name="Borgwardt"/><ref>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]].</ref> Like the simplex algorithm, the criss-cross algorithm visits exactly 3 additional corners of the three-dimensional cube on average.
==Variants==
Line 41:
===Vertex enumeration===
The criss-cross algorithm was used in an algorithm for [[Vertex enumeration problem|enumerating all the vertices of a polytope]], which was published by [[David Avis]] and [[Komei Fukuda]] in 1992.<ref>{{harvtxt|Avis|Fukuda|1992|p=297}}</ref> Avis and Fukuda presented an algorithm which finds the ''v'' vertices of a [[polyhedron]] defined by a nondegenerate system of ''n'' [[linear inequality|linear inequalities]] in ''D'' [[dimension (vector space)|dimension]]s (or, dually, the ''v'' [[facet]]s of the [[convex hull]] of ''n'' points in ''D'' dimensions, where each facet contains exactly ''D'' given points) in time [[Big Oh notation|O]](''nDv'') and O(''nD'') [[space complexity|space]].<ref>The ''v'' vertices in a simple arrangement of ''n'' [[hyperplane]]s in ''D'' dimensions can be found in O(''n''<sup>2</sup>''Dv'') time and O(''nD'') [[space complexity]].</ref>
===Oriented matroids===
| |||