|DATE:||Wednesday, May 26th 2004.|
|TIME:||4:30 PM - 5:00 PM|
|TITLE:||Building worst-case examples for the criss-cross method|
|SPEAKER:||Bohdan Kaluzny, McGill University|
The least-index criss-cross method is a pivot algorithm for solving linear programs that traverses the edges of the underlying oriented hyperplane arrangement of a convex polytope. Using deformed products of arrangements - an extension of deformed products of polytopes, we construct a family of linear programs with n inequalities in d-dimensions on which, in the worst-case, the least-index criss-cross method requires Omega(n^d) (for fixed d) pivots to reach optimality. This matches the upperbound as there can be at most O(n^d) vertices in an arrangement of hyperplanes.
Joint work with Komei Fukuda.