
Workshop on Approximation Algorithms for Hard Problems in Combinatorial
Optimization
Sunday, September 26, to Friday, October 1, 1999
TENTATIVE SCHEDULE
Sunday, September 26 
4:006:00 p.m.
 V. Vazirani
 Informal Registration and Refreshments at the Fields Institute

Monday, September 27 
10:00 a.m.
 V. Vazirani
 The primaldual schema for approximation algorithms: where does it stand,
and where can it go?

11:00 a.m.
 K. Jain
 An approximation algorithm for the kmedian problem through the facility
location problem

12:002:00 p.m.
 LUNCH at Fields 
2:00 p.m.
 M. Charikar
 An improved approximation for the kmedian problem

3:003:30 p.m.
 AFTERNOON TEA
 Local search and greedy improvement for facility location

3:304:30 p.m.
 S. Guha
 Local search and greedy improvement for facility location

4:305:30 p.m.
 F. Chudak
 Approximation algorithms for facility location

5:307:00 p.m.
 RECEPTION at Fields 
Tuesday, September 28 
9:30 a.m.
 U. Zwick
 Rounding solutions of semidefinite programs

10:3011:30 a.m.
 M. Skutella
 Convex quadratic relaxations and approximations for network scheduling

11:3012:30 a.m.
 M. Sviridenko
 New applications of the pipage rounding technique

12:302:30 p.m.

 Lunch 
2:30 p.m.
 C. Chekuri
 Approximation schemes for average weighted completion time scheduling
with release dates

3:304:00 p.m.
 AFTERNOON TEA 
4:005:00 p.m.
 D. Karger
 Approximation schemes for average completion time scheduling with release
dates

5:006:00 p.m.
 S. Khanna
 TBA

Wednesday, September 29 
9:30 a.m.
 U. Feige
 Approximating the minimum bisection size

10:3011:30 a.m.
 S. Rao
 Improved lowdistortion embeddings for planar graphs

11:30 a.m.
 M. Queyranne
 Sizeconstrained set partitioning with submodular costs

12:302:30
 Lunch

2:303:30
 RUMP SESSION

3:304:00 p.m.
 AFTERNOON TEA

4:006:00 p.m.
 RUMP SESSION 
Thursday, September 30 
9:3010:30 a.m.
 S. Arora
 Approximation algorithms that use a little advice

10:3011:30 a.m.
 J. Kleinberg
 Classification with pairwise relationships: metric labelling and Markov
random fields

11:3012:30 a.m.
 S. Vempala
 On the approximability of the Traveling Salesman Problem

12:302:30 p.m.

 Lunch 
2:303:30 p.m.
 Y. Rabani
 TBA

3:304:00 p.m.
 AFTERNOON TEA

4:306: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



