| DATE: | Wednesday, May 26th 2004. |
| TIME: | 4:30 PM - 5:00 PM |
| PLACE: | McConnel 320 |
| 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.