
SPECIAL YEAR ON GRAPH THEORY AND COMBINATORIAL OPTIMIZATION
Workshop on Polyhedral and Semidifinite Programming Methods
November 1  6, 1999
Monday, November 1 
Tuesday, November 2 
Wednesday, November 3 
2:004:00 p.m.
REGISTRATION at the Fields Institute
4:006:00 p.m.
COXETER LECTURE RECEPTION at Fields Institute
6:007:00 p.m.
COXETER LECTURE SERIES
Laszlo Lovasz, Microsoft Research
Geometric Representations Of Graphs: Lecture 1: Geometric Representations
and Graph Properties

9:3010:30 a.m.
Michel X. Goemans, Massachusetts Institute of Technology
When do semidefinite programs reduce to linear programs?
10:3011:00 a.m.
Coffee Break
11:0012:00 p.m.
Gerard Cornuejols, Carnegie Mellon University
Decomposition of perfect graphs, balanced matrices and ideal binary clutters
12:002:00 p.m.
Lunch
2:003:00 p.m.
William Cook and Sanjeeb Dash, Rice University
Some properties of the matrix cut operators of Lovasz and Schrijver
3:003:30 p.m.
Afternoon Tea
4:005:00 p.m.
COXETER LECTURE SERIES, II
Laszlo Lovasz, Microsoft Research
Orthogonal Representations and Semidefinite Optimization

9:3010:30 a.m.
Alexander Schrijver
CWI and University of Amsterdam A combinatorial, strongly polynomialtime
algorithm for submodular function minimization
10:3011:00 a.m.
Coffee Break
11:0012:00 p.m.
Robert Bixby, Rice University
TBA 12:002:00 p.m.
Lunch
2:003:00 p.m.
Laurence A. Wolsey, CORE, Catholic University of Louvain
From lotsizing to network design with cutting planes
3:003:30 p.m.
Afternoon Tea
4:005:00 p.m.
COXETER LECTURE SERIES, III
Laszlo Lovasz, Microsoft Research
Colin de Verdiere's Invariant


Thursday, November 4 
Friday, November 5 
Saturday, November 6 
9:3010:30 a.m.
Egon Balas, Carnegie Mellon University
Variations on a cut generating technique
10:3011:00 a.m.
Coffee Break
11:0012:00 p.m.
Masakuzu Kojima, Tokyo Institute of Technology
Global optimization via successive convex relaxation methods
12:002:00 p.m.
Lunch
2:003:00 p.m. Robert Weismantel, University of Magdeburg
Integral generating sets
3:003:30 p.m.
Afternoon Tea
3:304:00 p.m.
Lisa Fleischer, Columbia University
A combinatorial, strongly polynomial time algorithm for minimizing submodular
functions
4:004:30 p.m.
Sylvia Boyd, University of Ottawa
Working towards a proof of the 4/3 conjecture for the TSP
4:305:00 p.m.
Bruce Shepherd, Fundamental Mathematics, Bell Laboratories
Partitionable graphs and a refinement of rank
5:005:30 p.m. Gerald Gruber, University of Klagenfurt
Approximating Stable Sets Using the ThetaFunction and Cutting Planes

9:3010:30 a.m.
Maurice Queyranne, University of British Columbia
Scheduling Polyhedra: From cutting planes to approximation algorithms
10:3011:00 a.m.
Coffee Break
11:0012:00 p.m.
Andreas Schulz, Massachusetts Institute of Technology
Linear and quadratic programming relaxations and approximation algorithms
for scheduling problems
12:002:00 p.m.
Lunch
2:003:00 p.m.
Alexander Karzanov, Russian Academy of Sciences The multifacility location
problem and primitive extensions of metrics
3:003:30 p.m.
Afternoon Tea
3:304:00 p.m.
Laszlo Liptak, Yale University
The LovaszSchrijver operator and the stable set polytope
4:004:30 p.m. Lucia Moura, University of Toronto
Polytopes for Steiner designs and packings
4:305:00 p.m.
Kevin Wayne, Princeton University
A polynomial combinatorial algorithm for generalized minimum cost flow

9:0010:00 a.m.
Dimitris Bertsimas, Massachusetts Institute of Technology
Optimal inequalities in probability and finance using semidefinite optimization
10:0010:15
Coffee Break
10:1511:15 a.m.
David Williamson, IBM T.J. Watson Research
Twodimensional Gantt charts and a scheduling algorithm of Lawler
11:1511:30 a.m.
Coffee Break
11:3012:30 p.m.
Alexander Barvinok, University of Michigan
Quadratic convexity theorems via semidefinite programming
Workshop Ends


