Content deleted Content added
bibliography noting linear-fractional paper (so avoiding OR) |
→Other optimization problems with linear constraints: <ref name="Bibl"/> |
||
Line 33:
===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]].<ref name="FukudaNamikiLCP" >{{harvtxt|Fukuda|Namiki|1994|}}</ref><ref name="FTNamiki" >{{harvtxt|Fukuda|Terlaky|1997|p=385}}</ref><ref name="FukudaTerlaky"/><ref name="OMBook" >{{cite book|last=Björner|first=Anders|last2=Las Vergnas|first2=Michel|last3=Sturmfels|first3=Bernd|authorlink3=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter|authorlink5=Günter M. Ziegler|title=Oriented Matroids|chapter=10 Linear programming|publisher=Cambridge University Press|year=1999|isbn=9780521777506|url=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507|
|pages=417–479|doi=10.1017/CBO9780511586507|MR=1744046}}</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 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>
| |||