Criss-cross algorithm: Difference between revisions

Revision as of 05:12, 4 August 2011

Revision as of 05:22, 4 August 2011

Line 62:

</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.|authorlink=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|url=http://dx.doi.org/10.1016/0095-8956(85)90042-5|ref=harv}}</ref> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<ref name="OMBook"/>

When theThe criss-cross algorithm wasand published,its the simplicityproof of itsfinite statementtermination wascan remarkable,be assimply wasstated and readily extend the simplicitysetting of itsoriented finite-termination proofmatroids. FurtherThe algorithm can be simplificationfurther occurssimplified for ''linear feasibility problems'', that is for [[linear system]]s with [[linear inequality|nonnegative variable]]s,; especiallythese forproblems [[homogeneouscan system|homogeneousbe linearformulated system]]sfor oriented matroids.<ref name="KT91"/> Another remarkable feature of theThe criss-cross algorithm washas thatbeen itadapted wasfor readilyproblems adaptedthat toare more complicated problems.<refthan name="OMBook"/>linear programming: There are oriented-matroid variants of the criss-cross algorithmalso for the linear quadratic-programming problem (and its simplificationfor the linear feasibility-complementarity problem),<ref name="KT91"/> for the quadratic programming problem,.<ref name="FukudaTerlaky"/> and for the linear-complementarity problem.<ref name="FukudaNamikiLCP"/><ref name="OMBook"/>

==Summary==