Presented under the auspices of the Special Focus on Hardness of Approximation.
Monday, June 13, 2011
8:55 - 9:00 Opening
9:00 - 10:00 What have we learnt about graph expansion?
Sanjeev Arora
10:00 - 10:35 Approximation Algorithms for TSP
Amin Saberi
10:35 - 11:00 Break
11:00 - 12:00 A Postmortem of the Last Decade and Some Directions for the Future
Vijay Vazirani
12:00 - 1:30 Lunch
1:30 - 2:30 On the Unique Games Conjecture
Subhash Khot
2:30 - 3:05 Subexponential Algorithms for Unique Games and Related Problems
David Steurer
3:05 - 3:35 Break
3:35 - 4:10 Vertex-Connectivity Survivable Network Design
Sanjeev Khann
4:10 - 4:45 Approximation Algorithms for Discrepancy Problems
Nikhil Bansal
4:45 - 5:20 Why Do We Want a Good Ratio Anyway? Approximation
Stability and Proxy Objectives
Avrim Blum
Workshop dinner
Tuesday, June 14, 2011
9:00 - 10:00 Online Matching and the Adwords Market
Aranyak Metha
10:00 - 10:35 Generalized Online Matching with Concave Utilities
Kamal Jain
10:35 - 11:05 Break
11:05 - 11:40 Buy-at-bulk Network Design with Protection
Chandra Chekuri
11:40 - 12:15 Online Algorithms, the Primal-Dual Method,
and the k-Server Problem
Seffi Naor
12:10 - 1:45 Lunch
12:45 - 1:20 Lunch-time talk
Exponential Lower Bounds for Infinitary Payoff Game Policy
Iteration and Linear Program Simplex Methods
Oliver Friedman
1:45 - 2:20 Prize-collecting Frameworks
Mohammad Hajiaghayi
2:20 - 2:55 Approximation Algorithms for Stochastic Problems
Anupam Gupta
2:55 - 3:30 Network Design with Diseconomies of Scale
Lisa Zhang
3:30 - 4:00 Break
4:00 - 5:00 Iterative Methods in Combinatorial Optimization
Mohit Singh
Wednesday, June 15, 2011
9:00 - 10:00 Tree Decompositions for Congestion Minimization
Harald Raecke
10:00 - 10:35 Constructive Aspects of the Lovasz Local Lemma
and their Applications
Aravind Srinivasan
10:35 - 11:00 Break
11:00 - 12:00 PCPs and Inapproximability: Recent Milestones, and
New and Continuing Challenges
Venkat Guruswami
12:00 - 1:45 Lunch
12:45 - 1:20 Lunch-time Talk
Generalized Online Matching with Concave Utilities
Kamal Jain
1:45 - 2:20 Flow-cut Gaps and Hardness of Cut Problems in Directed Graphs
Sanjeev Khanna
2:20 - 2:55 Steiner Tree Approximation via Iterative Randomized Rounding
Fabrizio Grandoni
2:55 - 3:30 Allocating Goods to Maximize Fairness
Julia Chuzhoy
3:30 - 4:00 Break
4:00 - 5:00 The Edge-Disjoint Paths with Congestion problem: Algorithms,
Lower Bounds and Open Problems
Matthew Andrews
7:00 - 9:30 Open problem session
Thursday, June 16, 2011
9:00 - 10:00 Generic techniques to round SDP relaxations
Prasad Raghavendra
10:00 - 10:35 A Combinatorial, Primal-Dual Approach to Semidefinite Programs
Satyen Kale
10:35 - 11:05 Break
11:05 - 11:40 Discrete Extension and Selection Problems
Yuval Rabani
11:40 - 12:15 Approximating Metrics by Tree Metrics
Kunal Talwar
12:15 - 1:45 Lunch
1:45 - 2:20 Finding Dense Subgraphs
Moses Charikar
2:20 - 2:55 Approximability of Submodular Combinatorial Optimization
Problems
Pushkar Tripathi
2:55 - 3:30 Scheduling to Minimize Flow Time
Naveen Garg
3:30 - 4:00 Break
4:00 - 5:00 Introduction to LP and SDP hierarchies
Madhur Tulsiani
Friday, June 17, 2011
9:00 - 9:35 New Approximation Schemes for Optimization Problems in
Planar Graphs
Phil Klein
9:35 - 10:10 Beyond Planar Graphs: Minors, Bidimensionality, & Decomposition
Erik Demaine
10:00 - 10:35 Universal Approximations in Network Design
Rajmohan Rajaraman
10:35 - 11:00 Break
11:00 - 12:00 Approximation in Algorithmic Game Theory
Tim Roughgarden
Previous: Participation
Workshop Index
DIMACS Homepage