McGill University - School of Computer Science

Algorithms Seminar 2003

Everybody is welcome!

DATE: Thursday, March 27th
TIME: 4:15 PM - 5:15 PM
PLACE: McConnell 103
TITLE: Generating vertices and faces with symmetries
SPEAKER: Antoine Deza, Tokyo Institute of Technology

We study enumeration algorithms for polytopes that arise in combinatorial optimization problems. Enumerating these polytopes is usually practically intractable. But for specific problems, tailor-made algorithms, using the polytopes' rich combinatorial features, can be very efficient. The main engine of these combinatorial algorithms is the use of the large symmetry group of combinatorial polytopes. We present an orbitwise vertex enumeration algorithm to generate the 1 550 825 600 vertices of a highly degenerate 28-dimensional polytope defined by its 224 facets. We describe a promising heuristic that skips the highest degeneracies. A generalization to an orbitwise face enumeration algorithm is presented. Lastly, computational issues for the orbitwise vertex and face enumeration algorithms are discussed.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at , or .
Web Address: