The 2011 School on Approximability

About

The focus of this school will be the approximability of optimization problems. Traditionally, approximability used to be a two-pronged task divided into algorithms and complexity but recently, a lot of cross-fertilization is taking place and the boundaries between algorithms and complexity are blurring. One of the goals of this school would be to further bring down this divide and promote a holistic thinking about approximability, which should lead to exciting new developments in the area.

The school will bring together key contributors in this area to discuss these modern methods to a large research audience. In addition, the school will also have talks and open sessions for sharing new research and directions in approximability.

Organization

Co-Chairs

  • Naveen Garg, Indian Institute of Technology Delhi
  • Nisheeth Vishnoi, Microsoft Research India

Support from IISc and MSR India

  • G. Rangarajan (Convener, IISc Mathematics Initiative)
  • Vidya Natampally (Microsoft Research India, Director of Strategy)
  • Ashwani Sharma (Microsoft Research¬†India, Program Manager, External Research)

Agenda and Talks

Click here to download the complete program

Wednesday, January 5, 2011
0900 0930 Registration
0915 0945 Tea/Coffee
1000 1100 Richard M. Karp [Keynote Talk] (slides)
Effective Heuristics for NP-Hard Problems Arising in Molecular Biology
1100 1130 Tea/Coffee
1130 1230 Sanjeev Arora [Keynote Talk] (slides)
Semidefinite Programming and Approximation Algorithms: A Survey
1230 1400 Lunch
1400 1500 David Steurer (slides)
Algorithms for Unique Games and Related Problems
1500 1505 Break
1505 1605 Mohit Singh (slides)
A Randomized Rounding Approach to the Traveling Salesman Problem
1605 1630 Tea/Coffee
1630 1730 Ravi Kannan (slides)
Questions and Algorithms for Tensors
1730 1800 Amit Deshpande (slides)
Approximability of Subspace Approximation

 

Thursday, January 6, 2011
0930 1000 Tea/Coffee
1000 1100 R. Ravi (slides)
Matching Based Augmentations for Approximating Connectivity Problems
1100 1130 Tea/Coffee
1130 1230 Sanjeev Arora (slides)
Algorithms for Approximating Graph Expansion and Connections to Geometry
1230 1400 Lunch
1400 1500 David Steurer (slides)
Graph Expansion and the Unique Games Conjecture
1500 1505 Break
1505 1605 Lorenzo Orecchia (slides)
Fast Spectral Algorithms for Graph Partitioning and Graph Decomposition
1605 1630 Tea/Coffee
1630 1730 Subhash Khot (slides)
Introduction to Hardness of Approximation and Probabilistically Checkable Proofs
1730 1800 Saket Saurabh (slides)
Slightly Superexponential Parameterized Problems

 

Friday, January 7, 2011
0930 1000 Tea/Coffee
1000 1100 Subhash Khot (slides)
Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry
1100 1130 Tea/Coffee
1130 1230 Prasad Raghavendra (slides)
How to Round Any CSP?
1230 1400 Lunch
1400 1500 Nikhil Devanur (slides)
The Steiner Tree Problem
1500 1505 Break
1505 1605 Sambuddha Roy (slides)
Primal Dual Approximation Algorithms
1605 1630 Tea/Coffee
1630 1730 Kamal Jain (slides)
Online Bipartite Matching via a Primal-Dual Technique for Convex Programs
1730 1800 Vinayaka Pandit (slides)
Local Search Based Approximation Algorithms for Facility Location Problems

 

Saturday, January 8, 2011
0930 1000 Tea/Coffee
1000 1100 R. Ravi (slides)
Iterative Methods in Combinatorial Optimization
1100 1130 Tea/Coffee
1130 1230 Subhash Khot (slides)
On the Unique Games Conjecture
1230 1400 Lunch
1400 1500 Prasad Raghavendra (slides)
Complexity of Constraint Satisfaction Problems: Exact and Approximate
1500 1505 Break
1505 1605 Prahladh Harsha (slides)
Inapproximability Results from Label-Cover Variants and Other Hardness Assumptions
1605 1630 Tea/Coffee
1630 1730 Madhur Tulsiani (slides)
Introduction to LP and SDP Hierarchies
1730 1800 L. Sunil Chandran (slides)
Rainbow Colouring of Graphs

 

Sunday, January 9, 2011
0930 1000 Tea/Coffee
1000 1100 Amit Kumar (slides)
Scheduling to Minimize Weighted Flow-Time
1100 1130 Tea/Coffee
1130 1230 Naveen Garg (slides)
Fast Combinatorial Algorithms for Solving Positive Linear Programs
1230 1400 Lunch

Speakers