Groupe d’études et de recherche en analyse des décisions

The Criss-Cross Method Can Take Ω(nd) Pivots

K Fukuda et Bohdan Kaluzny

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.

, 22 pages