UIUC Computer Science Department

CS 583: Approximation Algorithms Chandra Chekuri

Spring 2016

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 1304.

Instructor:  Chandra Chekuri, 3228 Siebel Center, (chekuri at)

Teaching Assistant:  Vivek Madan, 3240 Siebel Center, (vmadan2 at)

Office Hours (Chandra): Tuesday, 1.30 - 2.30pm in 3228 Siebel

Office Hours (Vivek): Monday, 3 - 4pm in Siebel 3rd floor lounge

Grading Policy: There will be 6 homeworks, roughly once every two weeks. I expect all students to do the first 4. Students have the option of doing a course project in lieu of the last two homeworks (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 (now Theory II) 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.
  • 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.
• Iterative Methods in Combinatorial Optimization by Lau, Ravi and Singh.
• Geometric Approximation Algorithms book by Sariel Har-Peled, American Mathematical Society, 2011
• Notes and slides from previous editions of the course: Fall 2013, Spring 2011, Spring 2009 and Fall 2006.
• Books on related topics: Combinatorial Optimization (Schrijver), Randomized Algorithms (Motwani-Raghavan),  The Probabilistic Method (Alon-Spencer)
• 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.
• 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 based methods (rounding techniques, primal-dual, dual-fitting)
  • Metric methods
  • Semi-definite programming based methods
  Strenthening formulations including lift-and-project hierarchies
• Problems:
  • Tour problems: Metric-TSP, Asymmetric TSP, TSP Path, Orienteering
  • Scheduling: multiprocessor scheduling, precedence constraints
  • 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: knapsack, bin-packing, maximum independent set, packing integer programs
  • Constraint satisfaction: max and min CSP variants
  • Clustering and allocation: k-center, k-median, facility location, generalized assignment
  • 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

Homework:

Homework 0 (tex file) given on 01/20/2016, due in class on Friday 01/29/2016.

Homework 1 (tex file) given on 02/03/2016, due in class on Wednesday 02/17/2016.

Homework 2 (tex file) given on 02/17/2016, due in class on Wednesday 03/02/2016.

Homework 3 (tex file) given on 03/04/2016, due in class on Friday 03/18/2016.

Homework 4 (tex file) given on 03/28/2016, due in class on Friday 04/8/2016.

Homework 5 (tex file) given on 04/16/2016, due in class on Wednesday 04/27/2016.

Homework 6 (tex file) given on 04/27/2016, due on Monday 05/09/2016.

Lectures:

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

• Lecture 1: 1/20/2016, Introduction, Covering problems, Greedy for Set Cover

  • Chapter 1 in Williamson-Shmoys book
  • Chapters 1, 2 in Vazirani book
  • Notes from the past. Section 1 from Lecture 1 and Lecture 3

• Lecture 2: 1/22/2016, LP rounding for vertex cover, set cover

  • Chapter 1 in Williamson-Shmoys book
  • Chapters 13, 14, 15 in Vazirani book
  • Notes from the past. Lecture 4

• Lecture 3: 1/27/2016, Dual-fitting analysis for Set Cover, Additive vs Relative approx, Dominating Set Hardness

  • Chapter 1 in Williamson-Shmoys book
  • Chapters 13, 14, 15 in Vazirani book
  • Notes from the past. Lecture 4

• Lecture 4: 1/29/2016, PTAS and FPTAS for Knapsack

  • Chapter 3 in Williamson-Shmoys book
  • Chapter 8 in Vazirani book
  • Notes from the past. Lecture 6

• Lecture 5: 2/3/2016, Packing problems: maximum independent set, packing integer programs

  • Updated notes

• Lecture 6: 2/5/2016, Finish PIPs, Multiprocessor scheduling

  • Notes from the past.

• Lecture 7: 2/10/2016, Multiprocessor scheduling: PTAS, precedence constraints, inapproximability

  • Notes from the past.

• Lecture 8: 2/12/2016, Unrelated machine scheduling: randomized rounding and 2-approx

  • Notes from the past.
  • Chapter 17 in Vazirani book

• Lecture 9: 2/17/2016, Generalized assignment via iterated rounding, congestion minimization for routing

  • Short notes on rank lemma. See also Chapter 2 in book by Lau, Ravi, Singh (linked above).
  • Chapter 11.1 in Williamson-Shmoys book for generalized assignment
  • Chapter 5.11 in Williamson-Shmoys book for congestion minimization
  • For finer results on congestion minimization and related problems see Srinivasan's paper as well as recent results on Lovasz-Local-Lemma starting with Moser-Tardos paper.

• Lecture 10: 2/19/2016, Uncapacitated facility location: non-metric and metric

  • Chapter 4.5 in Williamson-Shmoys book

• Lecture 11: 2/24/2016, Clustering problems: k-center, k-median, and related. Intro to local search.

  • Chapters 2, 9 in Williamson-Shmoys book for local search and k-center, k-median
  • Chapter 5 in Vazirani book for k-center
  • Notes from the past on local search.

• Lecture 12: 2/26/2016, Local search for max-cut, submod-max, facility location, k-median.

  • Chapters 2, 9 in Williamson-Shmoys book for local search
  • Notes from the past on local search.

• Lecture 13: 3/2/2016, Finish previous lecture.

• Lecture 14: 3/4/2016, Start Network Design, Steiner Tree, Metric TSP.

  • Notes from the past. (Steiner tree, TSP)
  • Chapters 2, 9 in Williamson-Shmoys book for TSP and Steiner tree

• Lecture 15: 3/9/2016, ATSP, Intro to primal dual via vertex cover, feedback vertex set.

  • Chapter 7 in Willamson-Shmoys
  • Chapters 12, 15 in Vazirani
  • A survey by Jens Vygen on recent exciting development on Metric-TSP and ATSP and related problems.
  • A paper by Anari and Oveis Gharan which gives the current best integrality gap bound on ATSP using advanced techniques.

• Lecture 16: 3/11/2016, Primal dual for Steiner tree/forest.

  • Chapter 7 in Willamson-Shmoys
  • Chapter 22 in Vazirani

• Lecture 17: 3/16/2016, Steiner Network, Augmentation Framework, Abstract Network Design.

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

• Lecture 18: 3/18/2016, Covering skew-supermodular functions, iterated rounding approach of Jain.

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

• Lecture 19: 3/30/2016, 2-approx for Steiner Network via iterated rounding.

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

• Lecture 20: 4/1/2016, Finish counting argument for Steiner network iterated rounding. Intro to graph cut and partition problems.

• Lecture 21: 4/6/2016, 2-approx for Multiway Cut: edge, node, directed.

  • Notes from Fall 2006 on metric methods and edge multiway cut.
  • Chapter 8 in Williamson-Shmoys book
  • Chapters 4, 19 in Vazirani book
  • Recent paper on simple rounding for directed multiway cut

• Lecture 22: 4/8/2016, 1.5 approx for multiway cut.

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

• Lecture 23: 4/13/2016, Multicut, O(log k) approximation/flow-cut gap, lower bound via expanders.

  • 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 24: 4/13/2016, Sparsest cut and O(log^2 k) approximation via Multicut.

  • Chapters 8, 15 in Williamson-Shmoys book. See Prob 8.6.
  • Chapter 21 in Vazirani book

• Lecture 25: 4/20/2016, Intro to metric embeddings, Sparsest cut via l_1 embedding.

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

• Lecture 26: 4/22/2016, Finish sparsest cut via l_1 embedding, probabilistic tree embeddings.

  • Chaptera 8, 15 in Williamson-Shmoys book.
  • Notes from CMU class by Gupta and Ravi.

• Lecture 27: 4/27/2016, Intro to SDP, Max-Cut.

  • Chapter 6 in Williamson-Shmoys book.
  • Chapter 26 in Vazirani book.
  • Notes from 2006.

• Lecture 28: 4/29/2016, 3-Coloring via SDP.

  • Chapters 6, 13 in Williamson-Shmoys book.
  • Notes from 2006.

• Lecture 29: 5/4/2016, Hardness of approximation, closing thoughts.

  • Chapter 16 in Williamson-Shmoys book.
  • Chapter 29 in Vazirani book.