SPECIAL YEAR ON GRAPH THEORY AND COMBINATORIAL
OPTIMIZATION
Workshop on Polyhedral and Semidefinite Programming Methods
November 1 - 6, 1999
Organizing Committee
W. H. Cunningham,
University of Waterloo
W. R. Pulleyblank,
IBM Watson Research, New York
A. Schrijver,
CWI, Amsterdam
L. Tuncel,
University of Waterloo
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.
Invited speakers and participants include:
- Egon Balas, Carnegie Mellon University
- Alexander Barvinok, University of Michigan
- Dimitris Bertsimas, Massachusetts Institute of Technology
- Robert Bixby, Rice University
- William Cook, Rice University
- Gerard Cornuejols, Carnegie Mellon University
- Michel Goemans, Massachusetts Institute of Technology
- Alexander Karzanov, Russian Academy of Sciences
- Masakazu Kojima, Tokyo Institute of Technology
- László Lovász, Microsoft Research
- Maurice Queyranne, University of British Columbia
- Alexander Schrijver, CWI and University of Amsterdam
- Andreas Schulz, Massachusetts Institute of Technology
- Robert Weismantel, University of Magdeburg
- David Williamson, IBM T. J. Watson Research
- Laurence Wolsey, Catholic University of Louvain
This workshop is supported by the U.S. Office of Naval Research.
There will be two graduate courses offered during the Fall of 1999: Polyhedral
and Semidefinite Methods in Combinatorial Optimization and Approximation
Algorithms.
