Monday, June 7th

  9:00 - 9:05    Opening

Chair:              M. Karpinski 

 9:05 - 10:00    U. Feige,
                        On the Hardness of Approximating Hereditary Problems

10:15 - 10:50    L. Engebretsen,
                         More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP

11:00 - 11:35    M. Langberg, 
                         On Multicuts and Related Problems

11:45 - 12:20    A. Coja-Oghlan,
                         Coloring Semirandom Graphs Optimally

12:30                Lunch Break

 Chair:              R. Kannan

15:00 - 15:35    P. Drineas
                         Pass Efficient Algorithms for Approximating Large Matrices

15:45 - 16:20    M. Laurent
                         A PTAS for the Minimization of Polynomials of Fixed Degree over the Simplex

16:30 - 18:00    Special Sessions
                         16:30  Mathias Hauptmann, Steiner Tree Problems, (SemR I)
                         17:00  Lars Engebretsen, Query Efficient PCPs, (SemR III)

Tuesday, June 8th

Chair:              H.J. Prömel

 9:00 - 10:00    D. Hochbaum
                        Transformations to Totally Unimodular Matrices and Half-Integrality

10:15 - 10:50    T. Hayes
                         Coupling with Stationarity: Rapid Sampling for Graph Coloring

11:00 - 11:35    R. Reischuk
                         Robust Inference of Relevant Attributes

11:45 - 12:20    S. Hougardy
                         Approximation Algorithms for the Weighted Matching Problem

12:30                Lunch Break

Chair:               D. Hochbaum               

15:00 - 15:35   M. Cryan
                        The Natural Random Walk on the Transportation Polytope when the Number of Sources is Constant

15:45 - 16:20    K. Jansen
                        Approximation Algorithms for Mixed Packing and Covering Problems

16:30 - 18:00    Special Session
                         16:30 Nicolas Schabanel, Routing Problems in Distributed Networks

Wednesday, June 9th

Chair:              U. Feige

 9:00 - 10:00    J. Håstad
                        On the Advantage over a Random Assignment

10:15 - 10:50    M. Karpinski
                         Approximating Short Symmetric Instances of 3SAT

11:00 - 11:35    M. Bläser
                         Approximation Algorithms for Asymmetric Travelling Salesman Problem

11:45 - 12:20    S. Guha
                         An Omega(log^*n) Hardness of Approximation for the Asymmetric k-Center Problem

12:30                Lunch Break

13:30                Excursion

20:30               Evening Problem Session

Chair:               A. Barvinok

Thursday, June 10th

Chair:              J. Håstad

 9:00 - 10:00    M. Dyer
                        Counting Knapsack Solutions

10:15 - 10:50    R. Ravi
                         Boosted Sampling: Approximating Stochastic Programs

11:00 - 11:35    A. Steger
                         Average Case Analysis - Two Simple Problems

12:00               Lunch Break

Chair:              A. Steger

14:30 - 15:05   R. Kannan
                        Solving Maximum Satisfiability via Sampling

15:10 - 15:45   J. Chlebikova
                        Approximation Hardness of  Optimization Problems

15:55 - 16:30   M. Hauptmann
                        PTASs for Dense Steiner Tree Problems

16:40               Special Sessions
                       16:40   New PCP Results  (SemR. I)
                                   Chair:  J. Håstad

18:00              Dinner

19:00              Special Session
                       B. Vöcking, Approximating Combinatorial Auctions without Randomized Rounding,  (SemR II)

Friday, June 11th

Chair:              M. Dyer

 9:00 - 10:00   A. Barvinok
                       Fast and Crude Combinatorial Counting
                     
10:15 - 10:50   A. Czumaj
                        Sublinear Time Approximation for Metric MST and Facility Location Problems

11:00 - 11:35   B. Vöcking
                        Typical Properties of Winners and Losers in Discrete Optimization

12:30               Lunch

END OF WORKSHOP