McGill University - School of Computer Science

Computational Geometry Seminar

Everybody is welcome.

DATE:	Wednesday, November 5th, 1997
TIME:	12h00 - 13h00
PLACE:	McConnell 320N
TITLE:	"A New Paradigm for Finding Cutting Planes in the TSP"
SPEAKER:	Prof. Vasek Chvatal, Dept. Computer Science, Rutgers University

A traditional paradigm for finding cutting planes in the traveling salesman problem is this: having identified classes of linear inequalities (such as comb inequalities or clique-tree inequalities) that are satisfied by all tours, one designs "separation algorithms" for each individual class and finally applies these algorithms to an optimal solution of the current LP relaxation of the TSP instance. I will present another way of finding cutting planes, which does not fit this paradigm; preliminary computational experience with its implementation is encouraging.

These are results of joint work with David Applegate, Bob Bixby, and Bill Cook.

This information is available at http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to Therese Biedl at therese@cgm.cs.mcgill.ca.