April 16, 2014

Workshop: Approximation Algorithms: The Last Decade and the Next – June 13-17, 2011

June 13 – 17, 2011

The study of approximation algorithms for NP-hard problems has blossomed into a rich field, especially as a result of intense work over the last two decades. Furthermore, approximation has become a guiding principle for much of algorithm design in areas such as algorithmic game theory and economics, online computation, streaming algorithms, metric embeddings, and learning theory.  The Princeton Center for Computational Intractability and DIMACS are hosting a 5-day workshop,






Approximation Algorithms: The Last Decade and the Next

from June 13 to 17, 2011. This 5-day workshop will bring together researchers to focus on the important milestones achieved in this field over the last decade; prior work has been adequately covered in textbooks published a decade ago. This workshop will also attempt to set the tone for future work by identifying potentially fruitful areas, issues and questions. The discussion will be shaped by 10  hour-long survey talks, 20+ research talks, and informal discussion sessions.

Location: The workshop will take place in room 104 (large auditorium) at the CS Department. Please see this page for information regarding parking, wireless internet, airport shuttles  and other local services.

Organizing committee Sanjeev Arora (Princeton), Moses Charikar (Princeton), Sanjeev Khanna (U. Penn), Mohammad Taghi Hajiaghayi (U. Maryland and AT&T Labs), Vijay Vazirani (Georgia Tech), Lisa Zhang (Bell Labs)


Lodging: If you plan to come to the workshop and need a hotel room, we suggest that you reserve a room at the Nassau Inn as soon as possible. Their phone number is 1-800-862-7728  and you should ask for group number 14760 or `Approximation algorithms group' to get the special workshop rate (135$ + Tax for single or double occupancy rooms). The deadline for booking a room using the special rate is May 11 DO NOT BOOK YOUR ROOM ONLINE! THE SPECIAL RATE IS ONLY AVAILABLE WHEN MAKING A RESERVATION BY PHONE.



Dorms: We have a very limited number of dorm rooms at a rate of 49.50$ a person per night (single, air-conditioned rooms with semi-private bath). If you are interested in this option please send an email to local.approx11 including your name, the dates of your stay, and your gender (for room assignments). Please use 'Dorm request' as the subject line of your email.

[UPDATE:] There are no more dorm rooms available for the workshop.



Registration: Please use the form at the bottom of this page to register to the workshop. (Last minute registration is ok but please do not register on the last business day prior to the workshop).

Financial support: We have some limited funds to cover expenses of students attending the workshop. If you need such support please fill in the support request form at the bottom of this page. Once the workshop is over, you will also need to fill the following form: pu-expense-report. The forms should be submitted no later than 60 days after the workshop. Guidelines for filling the expense report are available here.If you are being reimbursed by PU  please read the following airfare guidelines carefully. All flights must be booked with a US flagship carrier airlines in order to receive reimbursement for the expense. Ask your travel agent or airline customer service representative if your flight will qualify if in doubt.

Important: If the travel includes stops in addition to the workshop location, appropriate documentation including the fare comparison direct to/from the conference location at the time of purchase must be included with the request for reimbursement. Documentation/comparisons cannot be dated  after the trip dates. Question regarding fare comparisons can be directed to Mitra Kelly (mkelly).

The Center for Computational Intractability especially encourages the participation in our workshops of researchers from backgrounds that are  traditionally underrepresented within the computer science research community.

Information for Speakers:  We cover local expenses (food and lodging) for all speakers. Speakers should reserve their hotel rooms on their own (see instruction above) using their credit card and we will arrange to pay for their rooms two weeks prior to the workshop. We also have some travel support available for speakers, but please let us know by April 15 if you think you might need it (send an email to approx.workshop). Speakers getting travel support are expected to use US flag carriers (NSF policy). If this makes travel much more expensive/inconvenient please let us know by April 15. We have a small amount of unrestricted funds that can be used to pay for flights on non-US carriers. Speakers who do not let us know by April 15 cannot rely on reimbursement."








Questions regarding the scientific program should be directed to approx.workshop .

For questions regarding local arrangements contact local.approx11

Confirmed speakers:

Sanjeev Arora, Venkat Guruswami [video], Subhash Khot [video], Aranyak Metha, Harald Raecke [video], Prasad Raghavendra, Tim Roughgarden, Mohit Singh [video], Madhur Tulsiani [video].
Regular talks:
Matthew Andrews, Nikhil Bansal [video], Avrim Blum [video], Moses Charikar [video], Chandra Chekuri, Julia Chuzhoy, Erik Demaine [video], Oliver Friedman, Naveen Garg [video], Fabrizio Grandoni, Anupam Gupta, Mohammad Hajiaghayi, Kamal Jain, Satyen Kale, Sanjeev Khanna [video], Phil Klein [video], Seffi Naor [video], Rajmohan Rajaraman, Amin Saberi , Aravind Srinivasan [video], David Steurer [video], Kunal Talwar [video], Pushkar Tripathi [video], Vijay Vazirani [video], Lisa Zhang [video].
You can use the form below to let us know of your impressions about the workshop (the program, speakers, local arrangements, etc). Your input will be very helpful for improving future workshops and in providing feedback to our sponsors.
My Fieldset
  1. (valid email required)
  2. (required)

cforms contact form by delicious:days



  1. [...] Center for Computational Intractability at Princeton University. The particular workshop is this one, the purpose being to recap the last decade of advances in this field and to set the direction for [...]

  2. [...] I am a bit concerned that – with a notable exception of the last year’s workshop in Princeton – I am not really aware of any forum that aims at reinforcing this kind of [...]

  3. [...] Center for Computational Intractability at Princeton University. The particular workshop is this one, the purpose being to recap the last decade of advances in this field and to set the direction for [...]