Approximation Algorithms: The Last Decade and the Next

June 13-17, 2011

Room 104 (Large Auditorium)

Department of Computer Science
Princeton University

Monday, June 13

9:00-10:00             Sanjeev Arora                       What Have We Learnt about Graph Expansion? [slides]

10:00-10:35           Mohit Singh                         Approximation Algorithms for TSP [slides]

11:00-12:00           Vijay Vazirani                      A Postmortem of the Last Decade and Some Directions for the Future [slides]

1:30-2:30               Subhash Khot                       On the Unique Games Conjecture [slides][survey]

2:30-3:05               David Steurer Subexponential Algorithms for Unique Games and Related Problems [slides]

3:35-4:10               Sanjeev Khanna                    Vertex-Connectivity Survivable Network Design [slides]

4:10-4:45               Nikhil Bansal                        Approximation Algorithms for Discrepancy Problems [slides][notes]

4:45-5:20               Avrim Blum                          Why Do We Want a Good Ratio Anyway? Approximation Stability and Proxy Objectives [slides] [notes]

Tuesday, June 14

9:00-10:00             Aranyak Mehta                     Online Matching and the Adwords Market [slides][notes]

10:00-10:35           Kamal Jain                            Understanding Karp-Vazirani-Vazirani’s Online Matching (1990) via Randomized Primal-Dual.

11:05-11:40           Chandra Chekuri                  Buy-at-bulk Network Design with Protection [slides]

11:40-12:15           Seffi Naor                             Online Algorithms, the Primal-Dual Method, and the k-Server Problem [slides] [notes]

12:45-1:20             Oliver Friedman                    Exponential Lower Bounds for Infinitary Payoff Game Policy Iteration and Linear Program Simplex Methods [slides] [notes]

1:45-2:20               Mohammad Hajiaghayi         Prize-collecting Frameworks [slides]

2:20-2:55               Anupam Gupta                     Approximation Algorithms for Stochastic Problems [slides]

2:55-3:30               Lisa Zhang                            Network Design with Diseconomies of Scale [slides]

4:00-5:00               Mohit Singh                          Iterative Methods in Combinatorial Optimization [slides]

Wednesday, June 15

9:00-10:00             Harald Raecke                      Tree Decompositions for Congestion Minimization [slides]

10:00-10:35           Aravind Srinivasan              Constructive Aspects of the Lovasz Local Lemma and their Applications [slides][notes]

11:00-12:00           Venkat Guruswami               PCPs and Inapproximability: Recent Milestones, and New and Continuing Challenges [slides]

12:45-1:20             Kamal Jain                            Generalized Online Matching with Concave Utilities 

1:45-2:20               Sanjeev Khanna                    Flow-cut Gaps and Hardness of Cut Problems in Directed Graphs [slides]

2:20-2:55               Fabrizio Grandoni                 Steiner Tree Approximation via Iterative Randomized Rounding [slides][notes]

2:55-3:30               Julia Chuzhoy                       Allocating Goods to Maximize Fairness [slides][notes]

4:00-5:00               Matthew Andrews                 The Edge-Disjoint Paths with Congestion problem: Algorithms, Lower Bounds and Open Problems [slides]

7:00-9:30              Open problem session [notes]

Thursday, June 16

9:00-10:00             Prasad Raghavendra             Generic techniques to round SDP relaxations [slides]

10:00-10:35           Satyen Kale                          A Combinatorial, Primal-Dual Approach to Semidefinite Programs [slides][notes]

11:05-11:40           Yuval Rabani                        Discrete Extension and Selection Problems [slides]

11:40-12:15           Kunal Talwar                        Approximating Metrics by Tree Metrics [slides]

1:45-2:20               Moses Charikar                     Finding Dense Subgraphs [slides]

2:20-2:55               Pushkar Tripathi Approximability of Submodular Combinatorial Optimization Problems [slides][notes]

2:55-3:30               Naveen Garg                         Scheduling to Minimize Flow Time [slides]

4:00-5:00               Madhur Tulsiani                   Introduction to LP and SDP hierarchies [slides]

Friday, June 17

9:00-9:35               Phil Klein                              New Approximation Schemes for Optimization Problems in Planar Graphs [slides] [notes]

9:35-10:10             Erik Demaine                        Beyond Planar Graphs: Minors, Bidimensionality, & Decomposition [slides] [notes]

10:00-10:35           Rajmohan Rajaraman           Universal Approximations in Network Design [slides] [notes]

11:00-12:00           Tim Roughgarden                 Approximation in Algorithmic Game Theory [slides]  [notes]