 |
Workshop on Approximation Algorithms for Hard Problems in Combinatorial
Optimization
Sunday, September 26, to Friday, October 1, 1999
TENTATIVE SCHEDULE
| Sunday, September 26 |
| 4:00-6:00 p.m.
| V. Vazirani
| Informal Registration and Refreshments at the Fields Institute
|
| Monday, September 27 |
| 10:00 a.m.
| V. Vazirani
| The primal-dual schema for approximation algorithms: where does it stand,
and where can it go?
|
| 11:00 a.m.
| K. Jain
| An approximation algorithm for the k-median problem through the facility
location problem
|
| 12:00-2:00 p.m.
| LUNCH at Fields |
| 2:00 p.m.
| M. Charikar
| An improved approximation for the k-median problem
|
| 3:00-3:30 p.m.
| AFTERNOON TEA
| Local search and greedy improvement for facility location
|
| 3:30-4:30 p.m.
| S. Guha
| Local search and greedy improvement for facility location
|
| 4:30-5:30 p.m.
| F. Chudak
| Approximation algorithms for facility location
|
| 5:30-7:00 p.m.
| RECEPTION at Fields |
| Tuesday, September 28 |
| 9:30 a.m.
| U. Zwick
| Rounding solutions of semidefinite programs
|
| 10:30-11:30 a.m.
| M. Skutella
| Convex quadratic relaxations and approximations for network scheduling
|
| 11:30-12:30 a.m.
| M. Sviridenko
| New applications of the pipage rounding technique
|
| 12:30-2:30 p.m.
|
| Lunch |
| 2:30 p.m.
| C. Chekuri
| Approximation schemes for average weighted completion time scheduling
with release dates
|
| 3:30-4:00 p.m.
| AFTERNOON TEA |
| 4:00-5:00 p.m.
| D. Karger
| Approximation schemes for average completion time scheduling with release
dates
|
| 5:00-6:00 p.m.
| S. Khanna
| TBA
|
| Wednesday, September 29 |
| 9:30 a.m.
| U. Feige
| Approximating the minimum bisection size
|
| 10:30-11:30 a.m.
| S. Rao
| Improved low-distortion embeddings for planar graphs
|
| 11:30 a.m.
| M. Queyranne
| Size-constrained set partitioning with submodular costs
|
| 12:30-2:30
| Lunch
|
| 2:30-3:30
| RUMP SESSION
|
| 3:30-4:00 p.m.
| AFTERNOON TEA
|
| 4:00-6:00 p.m.
| RUMP SESSION |
| Thursday, September 30 |
| 9:30-10:30 a.m.
| S. Arora
| Approximation algorithms that use a little advice
|
| 10:30-11:30 a.m.
| J. Kleinberg
| Classification with pairwise relationships: metric labelling and Markov
random fields
|
| 11:30-12:30 a.m.
| S. Vempala
| On the approximability of the Traveling Salesman Problem
|
| 12:30-2:30 p.m.
|
| Lunch |
| 2:30-3:30 p.m.
| Y. Rabani
| TBA
|
| 3:30-4:00 p.m.
| AFTERNOON TEA
|
| 4:30-6:00 p.m.
| CRM/Fields Prize Lecture
| Stephen Cook, University of Toronto, on the Achievements and Challenges
of Computational Complexity.
|
| Friday, October 1 |
| 9:30 a.m.
| N. Garg
| The minimum tree spanning k vertices
|
| 10:30 a.m.
| R. Ravi
| Approximation algorithms for group Steiner problems
|
| 11:30 a.m.-12:30 p.m.
| D. Williamson
| Improved approximation algorithms for MAX SAT
|
| 12:30 p.m.
| TBA
|
| 1:00 p.m.
|
| WORKSHOP ENDS
|
|
|
|
