Criss-cross algorithm

<h2 id="history">History</h2>
The criss-cross algorithm was published independently by <a href="/facts/Tamas_Terlaky/dLobLWrP">Tamas Terlaky</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> and by Zhe-Min Wang;<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> related algorithms appeared in unpublished reports by other authors.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h2 id="comparison-with-the-simplex-algorithm-for-linear-optimization">Comparison with the simplex algorithm for linear optimization</h2>
See also: <a href="/facts/Linear_programming/GduXFQxT">Linear programming</a>, <a href="/facts/Simplex_algorithm/9fndF6cq">Simplex algorithm</a>, and <a href="/facts/Bland%2527s_rule/XzVD9dfn">Bland's rule</a>

In linear programming, the criss-cross algorithm pivots between a sequence of bases but differs from the <a href="/facts/Simplex_algorithm/9fndF6cq">simplex algorithm</a>. The simplex algorithm first finds a (primal-) feasible basis by solving a "phase-one problem"; in "phase two", the simplex algorithm pivots between a sequence of basic feasible solutions so that the objective function is non-decreasing with each pivot, terminating with an optimal solution (also finally finding a "dual feasible" solution).<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
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 <a href="/facts/Bland%2527s_rule/XzVD9dfn">least-index pivoting rule of Bland</a>.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> Bland's rule uses only <a href="/facts/Sign_function/VADy9zQq">signs</a> of coefficients rather than their <a href="/facts/Real_number/R02gw5Pb">(real-number) order</a> 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.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> 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.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a><a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> The criss-cross algorithm has been applied to furnish constructive proofs of basic results in <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a>, such as the <a href="/facts/Farkas_lemma/FFvJdekz">lemma of Farkas</a>.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
While most simplex variants are monotonic in the objective (strictly in the non-degenerate case), most variants of the criss-cross algorithm lack a monotone merit function which can be a disadvantage in practice.

<h2 id="description">Description</h2>
The criss-cross algorithm works on a standard pivot tableau (or on-the-fly calculated parts of a tableau, if implemented like the revised simplex method). In a general step, if the tableau is primal or dual infeasible, it selects one of the infeasible rows / columns as the pivot row / column using an index selection rule. An important property is that the selection is made on the union of the infeasible indices and the standard version of the algorithm does not distinguish column and row indices (that is, the column indices basic in the rows). If a row is selected then the algorithm uses the index selection rule to identify a position to a dual type pivot, while if a column is selected then it uses the index selection rule to find a row position and carries out a primal type pivot.

<h2 id="computational-complexity-worst-and-average-cases">Computational complexity: Worst and average cases</h2>
The <a href="/facts/Time_complexity/77T62gmf">time complexity</a> of an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> counts the number of <a href="/facts/Arithmetic_operation/hvHwkbMV">arithmetic operations</a> sufficient for the algorithm to solve the problem. For example, <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a> requires on the <a href="/facts/Big_oh/weFFjSWg">order of</a> D3 operations, and so it is said to have polynomial time-complexity, because its complexity is bounded by a <a href="/facts/Cubic_polynomial/t67bqD6c">cubic polynomial</a>. There are examples of algorithms that do not have polynomial-time complexity. For example, a generalization of Gaussian elimination called <a href="/facts/Buchberger%2527s_algorithm/7z5q4K33">Buchberger's algorithm</a> has for its complexity an exponential function of the problem data (the <a href="/facts/Degree_of_a_polynomial/Bf8vEIhf">degree of the polynomials</a> and the number of variables of the <a href="/facts/Multivariate_polynomial/Lzak8VVx">multivariate polynomials</a>). Because exponential functions eventually grow much faster than polynomial functions, an exponential complexity implies that an algorithm has slow performance on large problems.
Several algorithms for linear programming—<a href="/facts/Khachiyan/GUyIPnxu">Khachiyan</a>'s <a href="/facts/Ellipsoidal_algorithm/K3SDpleG">ellipsoidal algorithm</a>, <a href="/facts/Karmarkar/NVB6kg95">Karmarkar</a>'s <a href="/facts/Karmarkar%2527s_algorithm/rprPV1Wu">projective algorithm</a>, and <a href="/facts/Interior-point_method/prIIrceN">central-path algorithms</a>—have polynomial time-complexity (in the <a href="/facts/Worst_case_complexity/kqzQkwIc">worst case</a> and thus <a href="/facts/Average_case_complexity/6TqLIMMz">on average</a>). The ellipsoidal and projective algorithms were published before the criss-cross algorithm.
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 2D corners of a (perturbed) cube in dimension D, according to a paper of Roos; Roos's paper modifies the <a href="/facts/Victor_Klee/NMRFBGm6">Klee</a>–Minty construction of a <a href="/facts/Unit_cube/S52tnk6m">cube</a> on which the simplex algorithm takes 2D steps.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a><a class="footnote-ref" id="fnref:21" href="#fn:21">21</a><a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> 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 <a href="/facts/Komei_Fukuda/H88HI0Q4">Fukuda</a> and Namiki.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a><a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> Trivially, the simplex algorithm takes on average D steps for a cube.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a><a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> Like the simplex algorithm, the criss-cross algorithm visits exactly 3 additional corners of the three-dimensional cube on average.

<h2 id="variants">Variants</h2>
The criss-cross algorithm has been extended to solve more general problems than linear programming problems.

<h3>Other optimization problems with linear constraints</h3>
There are variants of the criss-cross algorithm for linear programming, for <a href="/facts/Quadratic_programming/ct4RIUgs">quadratic programming</a>, and for the <a href="/facts/Linear_complementarity_problem/eSKsgl38">linear-complementarity problem</a> with "sufficient matrices";<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a><a class="footnote-ref" id="fnref:28" href="#fn:28">28</a><a class="footnote-ref" id="fnref:29" href="#fn:29">29</a><a class="footnote-ref" id="fnref:30" href="#fn:30">30</a><a class="footnote-ref" id="fnref:31" href="#fn:31">31</a><a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a><a class="footnote-ref" id="fnref:34" href="#fn:34">34</a> A sufficient matrix is a generalization both of a <a href="/facts/Positive-definite_matrix/Hbr6AuPS">positive-definite matrix</a> and of a <a href="/facts/P-matrix/XVgLSEbf">P-matrix</a>, whose <a href="/facts/Principal_minor/CMudF5Eh">principal minors</a> are each positive.<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a><a class="footnote-ref" id="fnref:36" href="#fn:36">36</a><a class="footnote-ref" id="fnref:37" href="#fn:37">37</a> The criss-cross algorithm has been adapted also for <a href="/facts/Linear-fractional_programming/00IY0jHQ">linear-fractional programming</a>.<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a><a class="footnote-ref" id="fnref:39" href="#fn:39">39</a>

<h3>Vertex enumeration</h3>
The criss-cross algorithm was used in an algorithm for <a href="/facts/Vertex_enumeration_problem/VT6MJ27t">enumerating all the vertices of a polytope</a>, which was published by <a href="/facts/David_Avis/ofybefml">David Avis</a> and <a href="/facts/Komei_Fukuda/H88HI0Q4">Komei Fukuda</a> in 1992.<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a> Avis and Fukuda presented an algorithm which finds the v vertices of a <a href="/facts/Polyhedron/UC0p9FTF">polyhedron</a> defined by a nondegenerate system of n <a href="/facts/Linear_inequality/YGHD3tW5">linear inequalities</a> in D <a href="/facts/Dimension_(vector_space)/z8m02A3W">dimensions</a> (or, dually, the v <a href="/facts/Facet/E3dBT4u9">facets</a> of the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of n points in D dimensions, where each facet contains exactly D given points) in time <a href="/facts/Big_Oh_notation/weFFjSWg">O</a>(nDv) and O(nD) <a href="/facts/Space_complexity/nsnAW5cV">space</a>.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a>

<h3>Oriented matroids</h3>

The criss-cross algorithm is often studied using the theory of <a href="/facts/Oriented_matroid/DTR8zRc6">oriented matroids</a> (OMs), which is a <a href="/facts/Combinatorics/k14xUoKT">combinatorial</a> abstraction of linear-optimization theory.<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a><a class="footnote-ref" id="fnref:43" href="#fn:43">43</a> Indeed, Bland's pivoting rule was based on his previous papers on oriented-matroid theory. However, Bland's rule exhibits cycling on some oriented-matroid linear-programming problems.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a> The first purely combinatorial algorithm for linear programming was devised by Michael J. Todd.<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a><a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> Todd's algorithm was developed not only for linear-programming in the setting of oriented matroids, but also for <a href="/facts/Quadratic_programming/ct4RIUgs">quadratic-programming problems</a> and <a href="/facts/Linear_complementarity_problem/eSKsgl38">linear-complementarity problems</a>.<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a><a class="footnote-ref" id="fnref:48" href="#fn:48">48</a> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<a class="footnote-ref" id="fnref:49" href="#fn:49">49</a>
The criss-cross algorithm and its proof of finite termination can be simply stated and readily extend the setting of oriented matroids. The algorithm can be further simplified for linear feasibility problems, that is for <a href="/facts/Linear_system/uEl20Kc1">linear systems</a> with <a href="/facts/Linear_inequality/YGHD3tW5">nonnegative variables</a>; these problems can be formulated for oriented matroids.<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a> The criss-cross algorithm has been adapted for problems that are more complicated than linear programming: There are oriented-matroid variants also for the quadratic-programming problem and for the linear-complementarity problem.<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a><a class="footnote-ref" id="fnref:52" href="#fn:52">52</a><a class="footnote-ref" id="fnref:53" href="#fn:53">53</a>

<h2 id="summary">Summary</h2>
The criss-cross algorithm is a simply stated algorithm for linear programming. It was the second fully combinatorial algorithm for linear programming. The partially combinatorial simplex algorithm of Bland cycles on some (nonrealizable) oriented matroids. The first fully combinatorial algorithm was published by Todd, and it is also like the simplex algorithm in that it preserves feasibility after the first feasible basis is generated; however, Todd's rule is complicated. The criss-cross algorithm is not a simplex-like algorithm, because it need not maintain feasibility. The criss-cross algorithm does not have polynomial time-complexity, however.
Researchers have extended the criss-cross algorithm for many optimization-problems, including linear-fractional programming. The criss-cross algorithm can solve quadratic programming problems and linear complementarity problems, even in the setting of oriented matroids. Even when generalized, the criss-cross algorithm remains simply stated.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Jack_Edmonds/4bLnep3e">Jack Edmonds</a> (pioneer of combinatorial optimization and oriented-matroid theorist; doctoral advisor of Komei Fukuda)</li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/David_Avis/ofybefml">Avis, David</a>; <a href="/facts/Komei_Fukuda/H88HI0Q4">Fukuda, Komei</a> (December 1992). <a href="https://doi.org/10.1007%2FBF02293050">"A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra"</a>. <a href="/facts/Discrete_and_Computational_Geometry/wVPxzUWo">Discrete and Computational Geometry</a>. 8 (ACM Symposium on Computational Geometry (North Conway, NH, 1991) number 1): 295–313. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02293050">10.1007/BF02293050</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1174359">1174359</a>.</li>
<li>Csizmadia, Zsolt; Illés, Tibor (2006). <a href="https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf">"New criss-cross type algorithms for linear complementarity problems with sufficient matrices"</a> (PDF). Optimization Methods and Software. 21 (2): 247–266. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F10556780500095009">10.1080/10556780500095009</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2195759">2195759</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:24418835">24418835</a>. Archived from <a href="http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf">the original</a> (pdf) on 23 September 2015. Retrieved 30 August 2011.</li>
<li><a href="/facts/Komei_Fukuda/H88HI0Q4">Fukuda, Komei</a>; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01582581">10.1007/BF01582581</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1286455">1286455</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:21476636">21476636</a>.</li>
<li><a href="/facts/Komei_Fukuda/H88HI0Q4">Fukuda, Komei</a>; <a href="/facts/Tam%25C3%25A1s_Terlaky/dLobLWrP">Terlaky, Tamás</a> (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373">10.1.1.36.9373</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02614325">10.1007/BF02614325</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1464775">1464775</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2794181">2794181</a>. <a href="http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps">Postscript preprint</a>.</li>
<li>den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). <a href="http://core.ac.uk/download/pdf/6714737.pdf">"The linear complementarity problem, sufficient matrices, and the criss-cross method"</a> (PDF). Linear Algebra and Its Applications. 187: 1–14. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0024-3795%2893%2990124-7">10.1016/0024-3795(93)90124-7</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1221693">1221693</a>.</li>
<li>Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). <a href="http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a">"The finite criss-cross method for hyperbolic programming"</a>. European Journal of Operational Research. 114 (1): 198–214. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0377-2217%2898%2900049-6">10.1016/S0377-2217(98)00049-6</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0953.90055">0953.90055</a>. <a href="http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz">Postscript preprint</a>.</li>
<li>Klafszky, Emil; Terlaky, Tamás (June 1991). <a href="https://doi.org/10.1016%2F0024-3795%2891%2990356-2">"The role of pivoting in proving some fundamental theorems of linear algebra"</a>. Linear Algebra and Its Applications. 151: 97–118. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0024-3795%2891%2990356-2">10.1016/0024-3795(91)90356-2</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1102142">1102142</a>.</li>
<li>Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1): 79–84. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01585729">10.1007/BF01585729</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1045573">1045573</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:33463483">33463483</a>.</li>
<li>Terlaky, T. (1985). "A convergent criss-cross method". Optimization: A Journal of Mathematical Programming and Operations Research. 16 (5): 683–690. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F02331938508843067">10.1080/02331938508843067</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0233-1934">0233-1934</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0798939">0798939</a>.</li>
<li><a href="/facts/Tam%25C3%25A1s_Terlaky/dLobLWrP">Terlaky, Tamás</a> (1987). <a href="https://doi.org/10.1016%2F0095-8956%2887%2990049-9">"A finite crisscross method for oriented matroids"</a>. Journal of Combinatorial Theory. Series B. 42 (3): 319–327. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2887%2990049-9">10.1016/0095-8956(87)90049-9</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0095-8956">0095-8956</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0888684">0888684</a>.</li>
<li><a href="/facts/Tam%25C3%25A1s_Terlaky/dLobLWrP">Terlaky, Tamás</a>; Zhang, Shu Zhong (1993) [1991]. "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46–47 (Degeneracy in optimization problems, number 1): 203–233. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7658">10.1.1.36.7658</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02096264">10.1007/BF02096264</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0254-5330">0254-5330</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1260019">1260019</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6058077">6058077</a>.</li>
<li>Wang, Zhe Min (1987). "A finite conformal-elimination free algorithm over oriented matroid programming". Chinese Annals of Mathematics (Shuxue Niankan B Ji). Series B. 8 (1): 120–125. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0252-9599">0252-9599</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0886756">0886756</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20110728105602/http://www.ifor.math.ethz.ch/~fukuda/">Komei Fukuda (ETH Zentrum, Zurich)</a> with <a href="https://web.archive.org/web/20110728105643/http://www.ifor.math.ethz.ch/~fukuda/publ/publ.html">publications</a></li>
<li><a href="http://coral.ie.lehigh.edu/~terlaky/">Tamás Terlaky (Lehigh University)</a> with <a href="http://coral.ie.lehigh.edu/~terlaky/publications">publications</a> <a href="https://web.archive.org/web/20110928051231/http://coral.ie.lehigh.edu/~terlaky/publications">Archived</a> 28 September 2011 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Illés, Szirmai & Terlaky (1999) - Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "The finite criss-cross method for hyperbolic programming". European Journal of Operational Research. 114 (1): 198–214. doi:10.1016/S0377-2217(98)00049-6. Zbl 0953.90055. Postscript preprint. <a href="http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a" target="_blank">http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Stancu-Minasian, I. M. (August 2006). "A sixth bibliography of fractional programming". Optimization. 55 (4): 405–428. doi:10.1080/02331930600819613. MR 2258634. S2CID 62199788. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Fukuda & Terlaky (1997) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Roos (1990) - Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483. <a href="https://doi.org/10.1007%2FBF01585729" target="_blank">https://doi.org/10.1007%2FBF01585729</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.). 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). New York-London: Academic Press. pp. 159–175. MR 0332165. <a href="/wiki/Victor_Klee" target="_blank">/wiki/Victor_Klee</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Fukuda & Terlaky (1997, p. 385) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Fukuda & Namiki (1994, p. 367) - Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636. <a href="https://doi.org/10.1007%2FBF01582581" target="_blank">https://doi.org/10.1007%2FBF01582581</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">The simplex algorithm takes on average D steps for a cube. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. MR 0868467. <a href="978-3-540-17096-9" target="_blank">978-3-540-17096-9</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Terlaky (1985) and Terlaky (1987) - Terlaky, T. (1985). "A convergent criss-cross method". Optimization: A Journal of Mathematical Programming and Operations Research. 16 (5): 683–690. doi:10.1080/02331938508843067. ISSN 0233-1934. MR 0798939. <a href="https://doi.org/10.1080%2F02331938508843067" target="_blank">https://doi.org/10.1080%2F02331938508843067</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Wang (1987) - Wang, Zhe Min (1987). "A finite conformal-elimination free algorithm over oriented matroid programming". Chinese Annals of Mathematics (Shuxue Niankan B Ji). Series B. 8 (1): 120–125. ISSN 0252-9599. MR 0886756. <a href="https://search.worldcat.org/issn/0252-9599" target="_blank">https://search.worldcat.org/issn/0252-9599</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Fukuda & Terlaky (1997) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Fukuda & Terlaky (1997) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Terlaky & Zhang (1993) - Terlaky, Tamás; Zhang, Shu Zhong (1993) [1991]. "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46–47 (Degeneracy in optimization problems, number 1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7658" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7658</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method". Mathematics of Operations Research. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. MR 0459599. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method". Mathematics of Operations Research. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. MR 0459599. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Bland's rule is also related to an earlier least-index rule, which was proposed by Katta G. Murty for the linear complementarity problem, according to Fukuda & Namiki (1994). <a href="/wiki/Linear_complementarity_problem" target="_blank">/wiki/Linear_complementarity_problem</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Fukuda & Terlaky (1997) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Terlaky & Zhang (1993) - Terlaky, Tamás; Zhang, Shu Zhong (1993) [1991]. "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46–47 (Degeneracy in optimization problems, number 1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7658" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7658</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Klafszky & Terlaky (1991) - Klafszky, Emil; Terlaky, Tamás (June 1991). "The role of pivoting in proving some fundamental theorems of linear algebra". Linear Algebra and Its Applications. 151: 97–118. doi:10.1016/0024-3795(91)90356-2. MR 1102142. <a href="https://doi.org/10.1016%2F0024-3795%2891%2990356-2" target="_blank">https://doi.org/10.1016%2F0024-3795%2891%2990356-2</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Fukuda & Terlaky (1997) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Roos (1990) - Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483. <a href="https://doi.org/10.1007%2FBF01585729" target="_blank">https://doi.org/10.1007%2FBF01585729</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.). 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). New York-London: Academic Press. pp. 159–175. MR 0332165. <a href="/wiki/Victor_Klee" target="_blank">/wiki/Victor_Klee</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Fukuda & Terlaky (1997, p. 385) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Fukuda & Namiki (1994, p. 367) - Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636. <a href="https://doi.org/10.1007%2FBF01582581" target="_blank">https://doi.org/10.1007%2FBF01582581</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">The simplex algorithm takes on average D steps for a cube. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. MR 0868467. <a href="978-3-540-17096-9" target="_blank">978-3-540-17096-9</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">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 unit sphere, as proved by Borgwardt and by Smale. <a href="/wiki/Euclidean_metric" target="_blank">/wiki/Euclidean_metric</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Fukuda & Terlaky (1997) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Fukuda & Terlaky (1997, p. 385) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Fukuda & Namiki (1994) - Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636. <a href="https://doi.org/10.1007%2FBF01582581" target="_blank">https://doi.org/10.1007%2FBF01582581</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046. <a href="978-0-521-77750-6" target="_blank">978-0-521-77750-6</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). "The linear complementarity problem, sufficient matrices, and the criss-cross method" (PDF). Linear Algebra and Its Applications. 187: 1–14. doi:10.1016/0024-3795(93)90124-7. <a href="http://core.ac.uk/download/pdf/6714737.pdf" target="_blank">http://core.ac.uk/download/pdf/6714737.pdf</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (PDF). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759. S2CID 24418835. Archived from the original (pdf) on 23 September 2015. Retrieved 30 August 2011. <a href="https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf" target="_blank">https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). "The linear complementarity problem, sufficient matrices, and the criss-cross method" (PDF). Linear Algebra and Its Applications. 187: 1–14. doi:10.1016/0024-3795(93)90124-7. <a href="http://core.ac.uk/download/pdf/6714737.pdf" target="_blank">http://core.ac.uk/download/pdf/6714737.pdf</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (PDF). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759. S2CID 24418835. Archived from the original (pdf) on 23 September 2015. Retrieved 30 August 2011. <a href="https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf" target="_blank">https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). "The linear complementarity problem, sufficient matrices, and the criss-cross method" (PDF). Linear Algebra and Its Applications. 187: 1–14. doi:10.1016/0024-3795(93)90124-7. <a href="http://core.ac.uk/download/pdf/6714737.pdf" target="_blank">http://core.ac.uk/download/pdf/6714737.pdf</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (PDF). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759. S2CID 24418835. Archived from the original (pdf) on 23 September 2015. Retrieved 30 August 2011. <a href="https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf" target="_blank">https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Cottle, R. W.; Pang, J.-S.; Venkateswaran, V. (March–April 1989). "Sufficient matrices and the linear complementarity problem". Linear Algebra and Its Applications. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. MR 0986877. <a href="/wiki/Richard_W._Cottle" target="_blank">/wiki/Richard_W._Cottle</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Illés, Szirmai & Terlaky (1999) - Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "The finite criss-cross method for hyperbolic programming". European Journal of Operational Research. 114 (1): 198–214. doi:10.1016/S0377-2217(98)00049-6. Zbl 0953.90055. Postscript preprint. <a href="http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a" target="_blank">http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Stancu-Minasian, I. M. (August 2006). "A sixth bibliography of fractional programming". Optimization. 55 (4): 405–428. doi:10.1080/02331930600819613. MR 2258634. S2CID 62199788. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Avis & Fukuda (1992, p. 297) - Avis, David; Fukuda, Komei (December 1992). "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra". Discrete and Computational Geometry. 8 (ACM Symposium on Computational Geometry (North Conway, NH, 1991) number 1): 295–313. doi:10.1007/BF02293050. MR 1174359. <a href="https://doi.org/10.1007%2FBF02293050" target="_blank">https://doi.org/10.1007%2FBF02293050</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">The v vertices in a simple arrangement of n hyperplanes in D dimensions can be found in O(n2Dv) time and O(nD) space complexity. <a href="/wiki/Hyperplane" target="_blank">/wiki/Hyperplane</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046. <a href="978-0-521-77750-6" target="_blank">978-0-521-77750-6</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">The theory of oriented matroids was initiated by R. Tyrrell Rockafellar. (Rockafellar 1969):Rockafellar, R. T. (1969). "The elementary vectors of a subspace of 
 
 
 
 
 R
 
 N
 
 
 
 
 {\displaystyle R^{N}}
 
 (1967)" (PDF). In R. C. Bose and T. A. Dowling (ed.). Combinatorial Mathematics and its Applications. The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press. pp. 104–127. MR 0278972. PDF reprint.Rockafellar was influenced by the earlier studies of Albert W. Tucker and George J. Minty. Tucker and Minty had studied the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm.
 <a href="/wiki/Oriented_matroid" target="_blank">/wiki/Oriented_matroid</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046. <a href="978-0-521-77750-6" target="_blank">978-0-521-77750-6</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046. <a href="978-0-521-77750-6" target="_blank">978-0-521-77750-6</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Todd, Michael J. (1985). "Linear and quadratic programming in oriented matroids". Journal of Combinatorial Theory. Series B. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. MR 0811116. <a href="/w/index.php?title=Michael_J._Todd_(mathematician)&action=edit&redlink=1" target="_blank">/w/index.php?title=Michael_J._Todd_(mathematician)&action=edit&redlink=1</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046. <a href="978-0-521-77750-6" target="_blank">978-0-521-77750-6</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Todd, Michael J. (1985). "Linear and quadratic programming in oriented matroids". Journal of Combinatorial Theory. Series B. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. MR 0811116. <a href="/w/index.php?title=Michael_J._Todd_(mathematician)&action=edit&redlink=1" target="_blank">/w/index.php?title=Michael_J._Todd_(mathematician)&action=edit&redlink=1</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046. <a href="978-0-521-77750-6" target="_blank">978-0-521-77750-6</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Klafszky & Terlaky (1991) - Klafszky, Emil; Terlaky, Tamás (June 1991). "The role of pivoting in proving some fundamental theorems of linear algebra". Linear Algebra and Its Applications. 151: 97–118. doi:10.1016/0024-3795(91)90356-2. MR 1102142. <a href="https://doi.org/10.1016%2F0024-3795%2891%2990356-2" target="_blank">https://doi.org/10.1016%2F0024-3795%2891%2990356-2</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Fukuda & Terlaky (1997) - Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">Fukuda & Namiki (1994) - Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636. <a href="https://doi.org/10.1007%2FBF01582581" target="_blank">https://doi.org/10.1007%2FBF01582581</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046. <a href="978-0-521-77750-6" target="_blank">978-0-521-77750-6</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
</ol>

Criss-cross algorithm open-in-new

Criss-cross algorithm