DIMACS and The Center for Computational Intractability Joint Workshop on Approximation Algorithms: The Last Decade and the Next

June 13 - 17, 2011
Princeton University

Organizers:
Sanjeev Arora, Princeton University
Moses Charikar, Princeton University
Sanjeev Khanna, U. Penn
Mohammad Taghi Hajiaghayi, U. Maryland and AT&T Labs
Vijay Vazirani, Georgia Tech
Lisa Zhang, Bell Labs
Contact information for organizers: approx.workshop at gmail.com.

Presented under the auspices of the Special Focus on Hardness of Approximation.


Workshop Program:

Program: http://intractability.princeton.edu.
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
Contacting the Center
Document last modified on June 10, 2011.