THEMATIC PROGRAMS

October 24, 2014

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:00--4:00 p.m.
REGISTRATION at the Fields Institute

4:00--6:00 p.m.
COXETER LECTURE RECEPTION at Fields Institute

6:00--7:00 p.m.
COXETER LECTURE SERIES
Laszlo Lovasz, Microsoft Research
Geometric Representations Of Graphs: Lecture 1: Geometric Representations and Graph Properties

9:30--10:30 a.m.
Michel X. Goemans, Massachusetts Institute of Technology
When do semidefinite programs reduce to linear programs?

10:30--11:00 a.m.
Coffee Break

11:00--12:00 p.m.
Gerard Cornuejols, Carnegie Mellon University
Decomposition of perfect graphs, balanced matrices and ideal binary clutters

12:00--2:00 p.m.
Lunch

2:00--3:00 p.m.
William Cook and Sanjeeb Dash, Rice University
Some properties of the matrix cut operators of Lovasz and Schrijver

3:00--3:30 p.m.
Afternoon Tea

4:00--5:00 p.m.
COXETER LECTURE SERIES, II
Laszlo Lovasz, Microsoft Research
Orthogonal Representations and Semidefinite Optimization

9:30--10:30 a.m.
Alexander Schrijver
CWI and University of Amsterdam A combinatorial, strongly polynomial-time algorithm for submodular function minimization

10:30--11:00 a.m.
Coffee Break

11:00--12:00 p.m.
Robert Bixby, Rice University

TBA 12:00--2:00 p.m.
Lunch

2:00--3:00 p.m.
Laurence A. Wolsey, CORE, Catholic University of Louvain
From lot-sizing to network design with cutting planes

3:00--3:30 p.m.
Afternoon Tea

4:00--5: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:30--10:30 a.m.

Egon Balas, Carnegie Mellon University
Variations on a cut generating technique

10:30--11:00 a.m.
Coffee Break

11:00--12:00 p.m.
Masakuzu Kojima, Tokyo Institute of Technology
Global optimization via successive convex relaxation methods

12:00--2:00 p.m.
Lunch

2:00--3:00 p.m. Robert Weismantel, University of Magdeburg
Integral generating sets

3:00--3:30 p.m.
Afternoon Tea

3:30--4:00 p.m.
Lisa Fleischer, Columbia University
A combinatorial, strongly polynomial time algorithm for minimizing submodular functions

4:00--4:30 p.m.
Sylvia Boyd, University of Ottawa
Working towards a proof of the 4/3 conjecture for the TSP

4:30--5:00 p.m.
Bruce Shepherd, Fundamental Mathematics, Bell Laboratories
Partitionable graphs and a refinement of rank

5:00--5:30 p.m. Gerald Gruber, University of Klagenfurt
Approximating Stable Sets Using the Theta-Function and Cutting Planes

9:30--10:30 a.m.
Maurice Queyranne, University of British Columbia
Scheduling Polyhedra: From cutting planes to approximation algorithms

10:30--11:00 a.m.
Coffee Break

11:00--12:00 p.m.
Andreas Schulz, Massachusetts Institute of Technology
Linear and quadratic programming relaxations and approximation algorithms for scheduling problems

12:00--2:00 p.m.
Lunch

2:00--3:00 p.m.
Alexander Karzanov, Russian Academy of Sciences The multifacility location problem and primitive extensions of metrics

3:00-3:30 p.m.
Afternoon Tea

3:30-4:00 p.m.
Laszlo Liptak, Yale University
The Lovasz--Schrijver operator and the stable set polytope

4:00--4:30 p.m. Lucia Moura, University of Toronto
Polytopes for Steiner designs and packings

4:30--5:00 p.m.
Kevin Wayne, Princeton University
A polynomial combinatorial algorithm for generalized minimum cost flow

9:00--10:00 a.m.

Dimitris Bertsimas, Massachusetts Institute of Technology
Optimal inequalities in probability and finance using semidefinite optimization

10:00--10:15
Coffee Break

10:15--11:15 a.m.
David Williamson, IBM T.J. Watson Research
Two-dimensional Gantt charts and a scheduling algorithm of Lawler

11:15--11:30 a.m.
Coffee Break

11:30--12:30 p.m.
Alexander Barvinok, University of Michigan
Quadratic convexity theorems via semidefinite programming

Workshop Ends