June 19, 2018

Workshop on Approximation Algorithms for Hard Problems in Combinatorial Optimization

Sunday, September 26, to Friday, October 1, 1999


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