Schedule

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.