Criss-cross algorithm: Difference between revisions

Revision as of 17:07, 24 June 2020

Latest revision as of 17:42, 23 June 2025

(19 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Method for mathematical optimization}}

{{About|an algorithm for mathematical optimization||Criss-cross (disambiguation){{!}}Criss-cross}}

{{Use dmy dates|date=DecemberJanuary 20132024}}

<!-- {{Context|date=May 2012}} -->

[[File:Unitcube.svg|thumb|right|alt=A three-dimensional cube|The criss-cross algorithm visits all&nbsp;8 corners of the [[Klee–Minty cube]] in the worst case. It visits&nbsp;3 additional corners on&nbsp;average. The Klee–Minty cube is a perturbation of the cube shown here.]]

In [[optimization (mathematics)|mathematical optimization]], the '''criss-cross algorithm''' is any of a family of [[algorithm]]s for [[linear programming]]. Variants of the criss-cross algorithm also solve more general problems with [[linear programming|linear inequality constraints]] and [[nonlinear programming|nonlinear]] [[optimization (mathematics)|objective functions]]; there are criss-cross algorithms for [[linear-fractional programming]] problems,<ref name="LF99Hyperbolic">{{harvtxt|Illés|Szirmai|Terlaky|1999}}</ref><ref name="Bibl" >{{cite journal|first=I.&nbsp;M.|last=Stancu-Minasian|title=A sixth bibliography of fractional programming|journal=Optimization|volume=55|number=4|date=August 2006|pages=405–428|doi=10.1080/02331930600819613|mr=2258634|s2cid=62199788}}</ref> [[quadratic programming|quadratic-programming]] problems, and [[linear complementarity problem]]s.<ref name="FukudaTerlaky" >{{harvtxt|Fukuda|Terlaky|1997}}</ref>

Like the [[simplex algorithm]] of [[George Dantzig|George B. Dantzig]], the criss-cross algorithm is not a [[time complexity|polynomial-time algorithm]] for linear programming. Both algorithms visit all&nbsp;2^''D''&nbsp;corners of a (perturbed) [[unit cube|cube]] in dimension&nbsp;''D'', the [[Klee–Minty cube]] (after [[Victor Klee]] and [[George J. Minty]]), in the [[worst-case complexity|worst case]].<ref name="Roos" >{{harvtxt|Roos|1990}}</ref><ref name="KleeMinty"/> However, when it is started at a random corner, the criss-cross algorithm [[Average-case complexity|on&nbsp;average]] visits only&nbsp;''D'' additional corners.<ref name="FTNamiki"/><ref name="FukudaNamiki"/><ref name="Borgwardt">The simplex algorithm takes on average&nbsp;''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|___location=Berlin|year=1987|pages=xii+268|isbn=978-3-540-17096-9|mr=868467|ref=harv}}</ref> Thus, for the three-dimensional cube, the algorithm visits all&nbsp;8 corners in the worst case and exactly&nbsp;3 additional corners on&nbsp;average.

==History==

Line 13 ⟶ 14:

{{See also|Linear programming|Simplex algorithm|Bland's rule}}

[[File:Simplex description.png|thumb|240px|In its second phase, the ''simplex algorithm'' crawls along the edges of the polytope until it finally reaches an optimum [[vertex (geometry)|vertex]]. The ''criss-cross algorithm'' considers bases that are not associated with vertices, so that some iterates can be in the ''interior ''of the feasible region, like interior-point algorithms; the criss-cross algorithm can also have ''infeasible'' iterates ''outside'' the feasible region.]]

In linear programming, the criss-cross algorithm pivots between a sequence of bases but differs from the [[simplex algorithm]] of [[George Dantzig]]. 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 when with an optimal solution (also finally finding a "dual feasible" solution).<ref name="FukudaTerlaky"/><ref name="TerlakyZhang">{{harvtxt|Terlaky|Zhang|1993}}</ref>

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|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|ref=harv}}</ref> Bland's rule uses only [[sign function|sign]]s of coefficients rather than their [[real number#Axiomatic approach|(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 name="Bland"/><ref>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"/> The criss-cross algorithm has been applied to furnish constructive proofs of basic results in [[real number|real]] [[linear algebra]], such as <!-- [[Steinitz's theorem|Steinitz's lemma]], --> the [[Farkas lemma|lemma of Farkas]]<!-- , [[Weyl's theorem]] on the finite generation of [[convex polytope]]s by linear inequalities ([[halfspace]]s), and the [[Krein–Milman theorem|Minkowski's theorem]] on [[extreme point]]s -->.<ref name="KT91" >{{harvtxt|Klafszky|Terlaky|1991}}</ref>

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.

==Description==

{{Expand section|date=April 2011}}

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.

==Computational complexity: Worst and average cases==

[[File:Ellipsoid 2.png|thumb|right<!-- 400px -->|The worst-case computational complexity of Khachiyan's ''ellipsoidal algorithm'' is a polynomial. The ''criss-cross algorithm'' has exponential complexity.]]

The [[time complexity]] of an [[algorithm]] counts the number of [[arithmetic operation]]s sufficient for the algorithm to solve the problem. For example, [[Gaussian elimination]] requires on the [[Big oh|order&nbsp;of]]''&nbsp;D''³ operations, and so it is said to have polynomial time-complexity, because its complexity is bounded by a [[cubic polynomial]]. There are examples of algorithms that do not have polynomial-time complexity. For example, a generalization of Gaussian elimination called [[Buchberger's algorithm]] has for its complexity an <!--doubly --> exponential function of the problem data (the [[degree of a polynomial|degree of the polynomial]]s and the number of variables of the [[multivariate polynomial]]s). Because exponential functions eventually grow much faster than polynomial functions, an<!-- attained rather than upper bound --> exponential complexity implies that an algorithm has slow performance on large problems.

Several algorithms for linear programming—[[Khachiyan]]'s [[ellipsoidal algorithm]], [[Karmarkar]]'s [[Karmarkar's algorithm|projective algorithm]], and [[interior-point method|central-path algorithm]]s—have polynomial time-complexity (in the [[worst case complexity|worst case]] and thus [[average case complexity|on&nbsp;average]]). 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&nbsp;2^''D''&nbsp;corners of a (perturbed) cube in dimension&nbsp;''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&nbsp;2^''D''&nbsp;steps.<ref name="FukudaTerlaky"/><ref name="Roos"/><ref name="KleeMinty">{{cite book|title=Inequalities&nbsp;III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September&nbsp;1–9,&nbsp;1969, dedicated to the memory of Theodore&nbsp;S. Motzkin)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|___location=New York-London|year=1972|mr=332165|last1=Klee|first1=Victor|authorlink1author-link1=Victor Klee|last2=Minty|first2= George&nbsp;J.|authorlink2author-link2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175|ref=harv}}</ref> Like the simplex algorithm, the criss-cross algorithm visits all&nbsp;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&nbsp;''D'' additional corners, however, according to a&nbsp;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&nbsp;''D'' steps for a cube.<ref name="Borgwardt"/><ref>More generally, for the simplex algorithm, the expected number of steps is proportional to&nbsp;''D'' for linear-programming problems that are randomly drawn from the [[Euclidean metric|Euclidean]] [[unit&nbsp;sphere]], as proved by Borgwardt and by [[Stephen Smale|Smale]].</ref> Like the simplex algorithm, the criss-cross algorithm visits exactly&nbsp;3 additional corners of the three-dimensional cube on&nbsp;average.

==Variants==

Line 38 ⟶ 37:

===Other optimization problems with linear constraints===

There are variants of the criss-cross algorithm for linear programming, for [[quadratic programming]], and for the [[linear complementarity problem|linear-complementarity problem]] with "sufficient matrices";<ref name="FukudaTerlaky"/><ref name="FTNamiki"/><ref name="FukudaNamikiLCP" >{{harvtxt|Fukuda|Namiki|1994|}}</ref><ref name="OMBook" >{{cite book|lastlast1=Björner|firstfirst1=Anders|last2=Las&nbsp; Vergnas|first2=Michel|author2-link=Michel Las Vergnas|last3=Sturmfels|first3=Bernd|authorlink3author-link3=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter|authorlink5author-link5=Günter M. Ziegler|title=Oriented Matroids|chapter=10 Linear programming|publisher=Cambridge University Press|year=1999|isbn=978-0-521-77750-6|pages=417–479|doi=10.1017/CBO9780511586507|mr=1744046}}</ref><ref name="HRT">{{cite journal|first1=D. |last1=den&nbsp; Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and Its Applications|volume=187|date=1 July 1993|pages=1–14|url=httphttps://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|doi-access=free}}</ref><ref name="CIsufficient">{{cite journal|first1=Zsolt|last1=Csizmadia|first2=Tibor|last2=Illés|title=New criss-cross type algorithms for linear complementarity problems with sufficient matrices|journal=Optimization Methods and Software|volume=21|year=2006|number=2|pages=247–266|doi=10.1080/10556780500095009|url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009-->|mr=2195759|s2cid=24418835|access-date=30 August 2011|archive-date=23 September 2015|archive-url=https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|url-status=dead}}</ref> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<ref name="HRT"/><ref name="CIsufficient"/> A [[sufficient&nbsp;matrix]] is a generalization both of a [[positive-definite matrix]] and of a [[P-matrix]], whose [[principal&nbsp;minor]]s are each positive.<ref name="HRT"/><ref name="CIsufficient"/><ref>{{cite journal|last1=Cottle|first1=R. W.|author-link1=Richard W. Cottle|last2=Pang|first2=J.-S.|last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear complementarity problem|journal=Linear Algebra and Its Applications|volume=114–115|date=March–April 1989|pages=231–249|doi=10.1016/0024-3795(89)90463-1|mr=986877|doi-access=free}}</ref> The criss-cross algorithm has been adapted also for [[linear-fractional programming]].<ref name="LF99Hyperbolic"/><ref name="Bibl"/>

url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009-->|mr=2195759|<!-- ref=harv -->}}</ref> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<ref name="HRT"/><ref name="CIsufficient"/> A [[sufficient&nbsp;matrix]] is a generalization both of a [[positive-definite matrix]] and of a [[P-matrix]], whose [[principal&nbsp;minor]]s are each positive.<ref name="HRT"/><ref name="CIsufficient"/><ref>{{cite journal|last1=Cottle|first1=R.&nbsp;W.|authorlink1=Richard W. Cottle|last2=Pang|first2=J.-S.|last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear&nbsp;complementarity problem|journal=Linear Algebra and Its Applications|volume=114–115|date=March–April 1989|pages=231–249|doi=10.1016/0024-3795(89)90463-1|mr=986877|ref=harv}}</ref> The criss-cross algorithm has been adapted also for [[linear-fractional programming]].<ref name="LF99Hyperbolic"/><ref name="Bibl"/>

===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&nbsp;1992.<ref>{{harvtxt|Avis|Fukuda|1992|p=297}}</ref> Avis and Fukuda presented an algorithm which finds the&nbsp;''v'' vertices of a [[polyhedron]] defined by a nondegenerate system of&nbsp;''n'' [[linear inequality|linear inequalities]] in&nbsp;''D'' [[dimension (vector space)|dimension]]s (or, dually, the&nbsp;''v'' [[facet]]s of the [[convex hull]] of&nbsp;''n'' points in&nbsp;''D'' dimensions, where each facet contains exactly&nbsp;''D'' given points) in time&nbsp;[[Big Oh notation|O]](''nDv'') and&nbsp;O(''nD'') [[space complexity|space]].<ref>The&nbsp;''v'' vertices in a simple arrangement of&nbsp;''n'' [[hyperplane]]s in&nbsp;''D'' dimensions can be found in&nbsp;O(''n''²''Dv'') time and O(''nD'') [[space complexity]].</ref>

===Oriented matroids===

[[File:max-flow min-cut example.svg|frame|right|The [[max-flow min-cut theorem]] states that the maximum flow through a network is exactly the capacity of its minimum cut. This theorem can be proved using the criss-cross algorithm for oriented matroids.]]

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 name="OMBook"/><ref>The theory of [[oriented matroid]]s was initiated by [[R.&nbsp;Tyrrell Rockafellar]]. {{harv|Rockafellar|1969}}:<p>{{cite book

|first=R.&nbsp; T.

|last=Rockafellar

|authorlinkauthor-link=R. Tyrrell Rockafellar

|chapter=The elementary vectors of a subspace of <math>R^N</math> (1967)

|pages=104–127

|editor=[[R. C. Bose]] and T.&nbsp; A. Dowling

|year=1969

|title=Combinatorial Mathematics and its Applications

Line 60 ⟶ 58:

|issue=4

|mr=278972

|chapter-url=http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf|ref=harv |id=[http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf PDF reprint]}}</p><p>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.</p>

</ref> 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.<ref name="OMBook"/> The first purely combinatorial algorithm for linear programming was devised by [[Michael J. Todd (mathematician)|Michael&nbsp;J. Todd]].<ref name="OMBook"/><ref name="Todd"/> Todd's algorithm was developed not only for linear-programming in the setting of oriented matroids, but also for [[quadratic programming|quadratic-programming problems]] and [[linear complementarity problem|linear-complementarity problem]]s.<ref name="OMBook"/><ref name="Todd" >{{cite journal|last=Todd|first=Michael&nbsp; J.|authorlinkauthor-link=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series&nbsp; B|volume=39|year=1985|number=2|pages=105–133|mr=811116|doi=10.1016/0095-8956(85)90042-5|refdoi-access=harvfree}}</ref> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<ref name="OMBook"/>

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 [[linear system]]s with [[linear inequality|nonnegative variable]]s; these problems can be formulated for oriented matroids.<ref name="KT91"/> 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.<ref name="FukudaTerlaky"/><ref name="FukudaNamikiLCP"/><ref name="OMBook"/>

Line 74 ⟶ 72:

==Notes==

{{Reflist}}

<references/>

==References==

* {{cite journal |first1=David |last1=Avis |first2=Komei |last2=Fukuda |authorlink2author-link2=Komei Fukuda |authorlink1author-link1=David Avis |title=A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra|journal=[[Discrete and Computational Geometry]] |volume=8 |date=December 1992 |pages=295–313 |doi=10.1007/BF02293050 |issue=ACM Symposium on Computational Geometry (North Conway, NH, 1991) number 1 |mr=1174359|ref=harv|doi-access=free }}

* {{cite journal|first1=Zsolt|last1=Csizmadia|first2=Tibor|last2=Illés|title=New criss-cross type algorithms for linear complementarity problems with sufficient matrices|journal=Optimization Methods and Software|volume=21|year=2006|number=2|pages=247–266|doi=10.1080/10556780500095009|url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009-->|mr=2195759|s2cid=24418835|access-date=30 August 2011|archive-date=23 September 2015|archive-url=https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|url-status=dead}}

* {{cite journal|last1=Fukuda|first1=Komei|author-link1=Komei Fukuda|last2=Namiki|first2=Makoto|title=On extremal behaviors of Murty's least index method|journal=Mathematical Programming|date=March 1994|pages=365–370|volume=64|number=1|doi=10.1007/BF01582581|mr=1286455|s2cid=21476636}}

url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009--> |mr=2195759|ref=harv}}

* {{cite journal|first1=Komei|last1=Fukuda|first1=Komei|authorlink1 author-link1=Komei Fukuda |first2=Tamás|last2=NamikiTerlaky|first2 author-link2=MakotoTamás Terlaky |title=OnCriss-cross extremalmethods: behaviorsA offresh Murty'sview leaston indexpivot algorithms method|journal=Mathematical Programming, Series B|datevolume=March 199479|pages=365–370369–395|volumeissue=64|Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3 |editor1-first=1Thomas M.|editor1-last=Liebling|editor2-first=Dominique|editor2-last=de Werra|year=1997|doi=10.1007/BF01582581BF02614325|refmr=harv1464775|mrid=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]|citeseerx=10.1.1.36.9373|s2cid=12864552794181}}

* {{cite journal|first1=D.|last1=den&nbsp; Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and Its Applications|volume=187|date=1 July 1993|pages=1–14|url=httphttps://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|ref=harv|mr=1221693|doi-access=free}}

* {{cite journal|first1=Komei|last1=Fukuda| authorlink1=Komei Fukuda |first2=Tamás|last2=Terlaky| authorlink2=Tamás Terlaky |title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming, Series B|volume=79|pages=369–395|issue=Papers from the&nbsp;16th International Symposium on Mathematical Programming held in Lausanne,&nbsp;1997, number 1–3 |editor1-first=Thomas&nbsp;M.|editor1-last=Liebling|editor2-first=Dominique|editor2-last=de&nbsp;Werra|year=1997|doi=10.1007/BF02614325|mr=1464775|ref=harv|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]|citeseerx=10.1.1.36.9373}}

* {{cite journal|first1=D.|last1=den&nbsp;Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and Its Applications|volume=187|date=1 July 1993|pages=1–14|url=http://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|ref=harv|mr=1221693}}

* {{<!-- citation -->cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|number=1|

pages=198–214|year=1999|<!-- |issn=0377-2217 -->|doi=10.1016/S0377-2217(98)00049-6|url=http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a

|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|zbl=0953.90055|id=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz Postscript preprint]|ref=harv}}

*{{cite journal|first1=Emil|last1=Klafszky|first2=Tamás|last2=Terlaky|title=The role of pivoting in proving some fundamental theorems of linear algebra|journal=Linear Algebra and Its Applications|volume=151|date=June 1991|pages=97–118|doi=10.1016/0024-3795(91)90356-2|url=http://www.cas.mcmaster.ca/~terlaky/files/pivot-la.ps|format=postscript|ref=harv|mr=1102142|doi-access-date=4 August 2011|archive-url=https://web.archive.org/web/20110927061207/http://www.cas.mcmaster.ca/~terlaky/files/pivot-la.ps|archive-date=27 September 2011|url-status=deadfree}}

* {{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|number=1|series=Series&nbsp; A|pages=79–84|doi=10.1007/BF01585729|mr=1045573|refs2cid=harv|33463483}}<!-- Google scholar reported no free versions -->}}

* {{cite journal|last=Terlaky|first=T.|title=A convergent criss-cross method|journal=Optimization: A Journal of Mathematical Programming and Operations Research|volume=16|year=1985|number=5|pages=683–690|issn=0233-1934|doi=10.1080/02331938508843067|ref=harv|mr=798939|}}<!-- Google scholar reported no free versions -->}}

* {{cite journal|last=Terlaky|first=Tamás|authorlinkauthor-link=Tamás Terlaky|title=A finite crisscross method for oriented matroids|volume=42|year=1987|number=3|pages=319–327|journal=Journal of Combinatorial Theory|series=Series&nbsp; B|issn=0095-8956|doi=10.1016/0095-8956(87)90049-9|mr=888684|refdoi-access=harv|free}}<!-- Google scholar reported no free versions -->}}

* {{cite journal|last1=Terlaky|first1=Tamás| authorlink1author-link1=Tamás Terlaky |last2=Zhang|first2=Shu&nbsp; Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|issue=Degeneracy in optimization problems, number 1 |journal=Annals of Operations Research|volume=46–47|year=1993|pages=203–233 |doi=10.1007/BF02096264|mr=1260019 |citeseerx = 10.1.1.36.7658 |s2cid=6058077| origyearorig-year = 1991 |issn=0254-5330|ref=harv}}

* {{cite journal|last=Wang|first=Zhe&nbsp; Min|title=A finite conformal-elimination free algorithm over oriented&nbsp; matroid programming|journal=Chinese Annals of Mathematics (Shuxue Niankan&nbsp; B&nbsp; Ji)|series=Series&nbsp; B|volume=8|year=1987|number=1|pages=120–125|issn=0252-9599|mr=886756|ref=harv|}}<!-- Google scholar reported no free versions -->}}

==External links==

* [https://web.archive.org/web/20110728105602/http://www.ifor.math.ethz.ch/~fukuda/ Komei Fukuda (ETH Zentrum, Zurich)] with [https://web.archive.org/web/20110728105643/http://www.ifor.math.ethz.ch/~fukuda/publ/publ.html publications]

* [http://coral.ie.lehigh.edu/~terlaky/ Tamás Terlaky (Lehigh University)] with [http://coral.ie.lehigh.edu/~terlaky/publications publications] {{Webarchive|url=https://web.archive.org/web/20110928051231/http://coral.ie.lehigh.edu/~terlaky/publications |date=28 September 2011 }}

{{Mathematical programming|state=expanded}}