{C}{C}{C}{C} UIUC Computer Science Department

CS 583: Approximation Algorithms Chandra Chekuri

Fall 2013

Course Summary

Approximation algorithms for NP-hard problems are polynomial time heuristics that have guarantees on the quality of their solutions. Such algorithms are one robust way to cope with intractable problems that arise in many areas of Computer Science and beyond. In addition to being directly useful in applications, approximation algorithms allow us to explore the structure of NP-hard problems and distinguish between different levels of difficulty that these problems exhibit in theory and practice. A rich algorithmic theory has been developed in this area and deep connections to several areas in mathematics have been forged. The first third to half of the course will provide a broad introduction to results and techniques in this area with an emphasis on fundamental problems and widely applicable tools. The second half of the course will focus on more advanced and specialized topics.

Administrative Information

Lectures: Wed, Fri 11:00am-12.15pm in Siebel Center 1302.

Instructor:  Chandra Chekuri, 3228 Siebel Center, chekuri at illinois

Teaching Assistant:  Nirman Kumar, 3240 Siebel Center, nkumar5 at illinois

Office Hours (Chandra): Monday 11am-noon

Office Hours (Nirman): Friday 3-4 PM

Grading Policy: There will be 6 homeworks, roughly once every two weeks. I expect all students to do the first 4. Students can either choose to do the two or do a course project (more information on topics forthcoming). Course projects could involve research on a specific problem or topic, a survey of several papers on a topic (summarized in a report and/or talk), or an application of approximation algorithms to some applied area of interest including experimental evaluation of specific algorithms.

Prerequisites: This is a graduate level class and a reasonable background in algorithms and discrete mathematics would be needed. Officially the prerequisite is CS 573 or equivalent. Knowledge and exposure to probability and linear programming is necessary. The instructor will try to make the material accessible to non-theory students who might be interested in applications. Consult the instructor if you have questions.

Study material:

• Recommended text books
  • The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011.
    Link points to free online non-printable version.
  • Approximation Algorithms by Vijay Vazirani, Springer-Verlag, 2004.
• Another useful book: Approximation Algorithms for NP-hard Problems, edited by Dorit S. Hochbaum, PWS Publishing Company, 1995.
• Notes and slides from previous editions of the course: Spring 2011, Spring 2009 and Fall 2006.
• Books on related topics: Combinatorial Optimization (Schrijver), Randomized Algorithms (Motwani-Raghavan),  The Probabilistic Method (Alon-Spencer)
• A draft of a book on Algorithms by Dasgupta, Papadimitriou and Vazirani.
• Lecture notes from various places: CMU (Gupta-Ravi).
• Jeff Erickson's algorithms lecture notes, old homeworks and exams and Sariel Har-Peled's lecture notes and problems on algorithms.
• Geometric Approximation Algorithms book by Sariel Har-Peled, American Mathematical Society, 2011.
  The page contains a link to an earlier version of the book available online.
• Notes and pointers to topics in combinatorial optimization from Chandra's course in Spring 2010

Tentative Topic List:

• Intro and Methodology: P vs NP, NP Optimization problems, Approximation Ratio, Additive vs Multiplicative, Pros and Cons.
• Techniques:
  • Greedy and combinatorial methods
  • Local search
  • Dynamic programming and approximation schemes
  • Linear programming rounding methods (randomized, primal-dual, dual-fitting, iterated rounding)
  • Semi-definite program based rounding
  • Metric methods
• Problems:
  • Tour problems: Metric-TSP, Asymmetric TSP, TSP Path, Orienteering
  • Number Problems: knapsack, bin packing
  • Scheduling: multiprocessor scheduling, precedence constraints, generalized assignment
  • Connectivity and network design: Steiner trees, Steiner forests, Buy at bulk network design, Survivable Network Design
  • Covering problems: vertex cover, set cover and generalizations
  • Packing problems: maximum independent set, packing integer programs
  • Constraint satisfaction: max k-Sat
  • Clustering: k-center, k-median, facility location
  • Cut problems: max cut, multiway cut, k-cut, multicut, sparsest cut, bisection
  • Routing problems: congestion minimization, maximum disjoint paths, unsplittable flow
• Hardness of approximation: simple proofs, approximation preserving reductions, some known results

 

Note: The above list is tentative. Not all of the material can be covered in one semester.

Resources:

Piazza signup

Moodle site

Homework:

Homework 0 (tex file) given on 08/28/2013, due in class on Friday 09/06/2013.

Homework 1 (tex file) given on 09/06/2013, due on Friday 09/20/2013.

Homework 2 (tex file) given on 09/21/2013, due on Monday 10/07/2013.

Homework 3 (tex file) given on 10/05/2013, due on Monday 10/21/2013.

Homework 4 (tex file) given on 10/21/2013, due on Monday 11/04/2013.

Homework 5 (tex file) given on 11/04/2013, due on Friday 11/22/2013.

Homework 6 (tex file) given on 11/22/2013, due on Monday 12/09/2013.

Lectures:

Warning: Notes may contain errors. Please bring those to the attention of the instructor.

• Lecture 1: 8/28/2013, Introduction and covering problems (vertex cover, dominating set, set cover)

  • Chapter 1 in Williamson-Shmoys book
  • Chapters 1, 2 in Vazirani book
  • Notes from Spring 2011 lectures (Lectures 1, 3)

• Lecture 2: 8/30/2013, Analyis of Greedy for set cover, LP rounding for vertex cover, set cover

  • Chapter 1 in Williamson-Shmoys book
  • Chapters 13, 14, 15 in Vazirani book
  • Notes from Spring 2011 lectures (Lectures 3, 4)

• Lecture 3: 9/6/2013, Set Cover via dual fitting, Packing problems: Max Indep Set, Knapsack

  • Chapters 1, 3 in Williamson-Shmoys book
  • Chapters 13, 14, 15, and 8 in Vazirani book
  • Notes from Spring 2011 lectures (Lectures 5, 6, 7)

• Lecture 4: 9/4/2013, PTAS and FPTAS for Knapsack

  • Chapter 3 in Williamson-Shmoys book
  • Chapter 8 in Vazirani book
  • Notes from Spring 2011 lectures (Lecture 6)

• Lecture 5: 9/11/2013  Multiprocessor Scheduling: 2-approximation and hardness

  • Notes from Spring 2009 lecture (Lectures 5, 6)

• Lecture 6: 9/13/2013 PTAS for Multiprocessor Scheduling, Greedy and APTAS for Bin Packing

  • Notes from Spring 2009 lecture (Lectures 5, 6)

• Lecture 7: 9/18/2013 Local search for Max-Cut, Submodular function maximization

  • Notes from Spring 2011 lectures (Lecture 12)

• Lecture 8: 9/20/2013 Finish local search for Submodular function maximization. Local search for bounded-degree spanning tree.

  • Williamson-Shmoys book - Sections 2.6 and 9.3

• Lecture 9: 9/25/2013 Finish bounded-degree spanning tree. 2-approximation for k-center, mention local-search for k-median and approximation bound.

  • For location and clustering problems see pointers from Spring 2011 lectures (Lectures 13, 14)

• Lecture 10: 9/27/2013 LP background for approximation

• Lecture 11: 10/02/2013 Randomized rounding for congestion minimization

  • Section 5.11 in Williamson-Shmoys book
  • Chapter 4 in Motwani-Raghavan book on randomized algorithms

• Lecture 12: 10/04/2013 Start Network Design: Steiner tree, Metric-TSP

  • Notes from Spring 2011 (Lectures 1,2)
  • The current best approximation for Steiner tree is in this paper.
  • A survey by Jens Vygen on recent exciting development on Metric-TSP and ATSP and related problems.

• Lecture 13: 10/09/2013 Primal-dual for Vertex Cover and then on to Steiner Forest

  • Williamson-Shmoys Chapter 7
  • Vazirani Chapters 15 and 22
  • Notes from Spring 2011 (Lecture 16)

• Lecture 14: 10/11/2013 Finish Primal-dual for Steiner Forest

• Lecture 15: 10/16/2013 Steiner Network, Augmentation Framework, Abstract Network Design

  • Survey by Goemans and Williamson on primal-dual for network design

• Lecture 16: 10/18/2013 Finish primal-dual for skew-supermodular functions

• Lecture 17: 10/23/2013 Iterated rounding for Steiner Network

  • Chapter 8 in Williamson-Shmoys book
  • Chapter 23 in Vazirani book

• Lecture 18: 10/25/2013 Finish Iterated rounding for Steiner Network

• Lecture 19: 10/30/2013 Intro to graph cut and partitioning problems and metric methods: multiway cut

  • Slides from Fall 2006 course.
  • Chapter 8 in Williamson-Shmoys book
  • Chapter 19 in Vazirani book

• Lecture 20: 11/01/2013 3/2-approximation for multiway cut and symmetric submodular multiway partition

  • Chapter 8 in Williamson-Shmoys book
  • Chapter 19 in Vazirani book
  • Paper on submodular multiway partition

• Lecture 21: 11/06/2013 Multicut

  • Notes from 2009 on multicut. The algorithm in the notes is different from the region growing ones given in the books below.
  • Chapter 8 in Williamson-Shmoys book
  • Chapter 20 (also Chapter 18) in Vazirani book

• Lecture 22: 11/08/2013 Sparsest cut via Multicut

  • See draft notes of Lecture 19 from Spring 2009 and Prob 8.6 from Williamson-Shmoys book.

• Lecture 23: 11/13/2013 Intro to metric embeddings and Sparsest cut via l_1 embedding

  • Chapters 8, 15 from Williamson-Shmoys book.
  • Chapter 21 in Vazirani book.
  • Lecture notes on metric embeddings by Matousek. Also a chapter on emebdding finite metric spaces in normed spaces.

• Lecture 24: 11/15/2013 Probabalistic Tree Embeddings

  • Notes from CMU class by Blum and Gupta
  • Chapters 8, 15 from Williamson-Shmoys book.

• Lecture 25: 11/20/2013 Intro to SDP and application to Max-Cut

  • Chapter 6 of Willamson-Shmoys and Chapter 26 from Vazirani

• Lecture 26: 11/22/2013 SDP for Coloring

  • Chapter 13 of Willamson-Shmoys
  • Notes from Spring 2006 version of course

• Lecture 27: 12/03/2013 Finish SDP for Coloring, mention SDP for Sparsest Cut

  • Chapter 15 of Willamson-Shmoys for uniform sparsest cut via SDP

• Lecture 28: 12/05/2013 Hardness of approximation

  • Chapter 16 of Willamson-Shmoys and Chapter 29 of Vazirani

 

Course Project Information