G-2004-03
The Criss-Cross Method Can Take Ω(nd) Pivots
and BibTeX reference
Using deformed products of arrangements, we construct a family of linear programs with n inequalities in d on which, in the worst-case, the least-index criss-cross method requires Ω (nd) (for fixed d) pivots to reach optimality.
Published January 2004 , 22 pages
Document
G-2004-03.pdf (200 KB)