Content deleted Content added
→Oriented matroids: feasibility problems KT91 |
|||
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 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 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=harv}}</ref> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<ref name="OMBook"/>
When the criss-cross algorithm was published, the simplicity of its statement was remarkable, as was the simplicity of its finite-termination proof. Further simplification occurs for ''linear feasibility problems'', that is for [[linear system]]s with [[linear inequality|nonnegative variable]]s, especially for [[homogeneous system|homogeneous linear system]]s.<ref name="KT91"/> Another remarkable feature of the criss-cross algorithm was that it was readily adapted to more complicated problems.<ref name="OMBook"/> There are oriented-matroid variants of the criss-cross algorithm for the linear programming problem
==Summary==
| |||