McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at