Atlas home || Conferences | Abstracts | about Atlas
Host: Fields Institute
Sponsor: U.S. Office of Naval Research
Homepage: http://www.fields.utoronto.ca/gt-polyhedral.html
Email: polyhedral@fields.utoronto.ca
Organizers: W. H. Cunningham (University of Waterloo), W. R. Pulleyblank (IBM Watson Research, New York), A. Schrijver (CWI, Amsterdam), L. Tuncel (University of Waterloo)
Description:
Polyhedral (linear programming) methods have been used to solve combinatorial optimization problems since the 1950's. They
have provided effective methods for attacking NP-hard problems like the travelling salesman problem, but they have also
provided the first proofs that numerous problems are solvable in polynomial time. Finally, the study of the combinatorial
structure of polyhedra associated with combinatorial problems has led to many beautiful results, connecting combinatorial
optimization with other parts of mathematics.
In the 1990's, a new technique, semidefinite programming, has been applied to combinatorial optimization problems. The semidefinite programming problem is the problem of optimizing a linear function of matrix variables subject to finitely many linear inequalities and the positive semidefiniteness condition on the matrix variables. For certain combinatorial problems semidefinite programming techniques have yielded remarkable new results; the most striking of these have occurred in the work of Goemans and Williamson on the maximum cut problem.
The goal of this workshop is to improve our understanding of the relationships between these two areas and how these two methods complement each other in producing more efficient methods for solving combinatorial optimization problems.
Coxeter Lecture Series: Dr. Lászl Lovász will give three talks in this Fields Institute lecture series during the workshop.
Date received: September 30, 1999
© 2008 Atlas Conferences Inc.