CS 583: Approximation Algorithms, Spring 2018

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: Tue, Thu 9.30am-10.45am in Siebel Center 1105.

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

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

Office Hours (Chandra): Thu 3.45-4.45pm, 3228 Siebel

Office Hours (Vivek): Tue 2-3pm, 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. You can consult the instructor if you wish to do less home works for a longer course project

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 by Sariel Har-Peled, American Mathematical Society, 2011
• Notes and slides from previous editions of the course: Spring 2016, 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), CMU2 (Gupta), EPFL (Svensson) .
• Jeff Erickson's algorithms lecture notes, old homeworks and exams
• Notes and pointers to topics in combinatorial optimization from Chandra's course in Spring 2010

Piazza Gradescope

Homework 0 (tex file) given on 01/16/2018, due in class on Thursday 01/25/2018.

Homework 1 (tex file) given on 01/25/2018, due on Thursday 02/08/2018.

Homework 2 (tex file) given on 02/08/2018, due on Thursday 02/22/2018.

Homework 3 (tex file) given on 02/23/2018, due on Thursday 03/08/2018.

Homework 4 (tex file) given on 03/10/2018, due on Thursday 03/30/2018.

Homework 5 (tex file) given on 04/05/2018, due on Friday 04/20/2018.

Homework 6 (tex file) given on 04/20/2018, due on Friday 05/04/2018.

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
  • Intro and Covering

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

  • Chapter 1 in Williamson-Shmoys book
  • Chapters 13, 14, 15 in Vazirani book
  • Covering

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

  • Chapter 1 in Williamson-Shmoys book for Set Cover, Chapter 16 on hardness
  • Chapters 13 in Vazirani book for Set Cover, Chapter 29 on Hardness of Approximation
  • Covering

• Lecture 4: 1/25/2018, PTAS and FPTAS for Knapsack

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

• Lecture 5: 1/30/2018, Packing problems: maximum independent set, packing integer programs

  • Notes
  • Paper of Borodin and Ye on elimination graphs and generalization.

• Lecture 6: 2/1/2018, Finish packing

• Lecture 7: 2/6/2018, Scheduling problems. Graham's list scheduling and PTAS for parallel machines

  • Notes from the past.

• Lecture 8: 2/8/2018, Multiprocessor scheduling with precedence constraints, Bin Packing

  • Notes from the past.

• Lecture 9: 2/13/2018, Unrelated machine scheduling and congestion minimization: randomized rounding and Chernoff bounds

  • Chapter 5.11 in Williamson-Shmoys book for congestion minimization
  • Notes on Chernoff bounds from Sariel Har-Peled. Also a cheat sheet.
  • 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 and applications/refinements in paper of Haeupler, Saha and Srinivasan.

• Lecture 10: 2/15/2018, Unrelated machine scheduling

  • Notes from the past.
  • 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

• Lecture 11: 2/20/2018, Intro to local search: Max Cut and Submodular Function Maximization.

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

• Lecture 12: 2/22/2018, k-center and start facility location

  • Chapter 2 in Williamson-Shmoys book for k-center (Gonzalez's algorithm)
  • Chapter 5 in Vazirani book for k-center (the bottleneck algorithm)

• Lecture 13: 2/27/2018, Uncapacitated facility location: non-metric and metric

  • Chapter 4.5 in Williamson-Shmoys book. Also see Chapter 9 for local search and a greedy algorithm.

• Lecture 14: 3/1/2018, Local search for k-median

  • Chapter 9 in Williamson-Shmoys book.

• Lecture 15: 3/6/2018, 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 16: 3/8/2018, ATSP, Intro to primal dual via vertex cover.

  • 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 recent breakthrough paper by Svensson, Tarnawski and Vegh which gives the first constant factor approximation for ATSP (via LP).

• Lecture 17: 3/13/2018 (by Vivek Madan), More on primal dual: feedback vertex set and shortest paths.

  • Chapter 7 in Willamson-Shmoys

• Lecture 18: 3/15/2018 (by Vivek Madan), Primal dual for Steiner forest.

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

• Lecture 19: 3/27/2018, Steiner Network, Abstract Network Design.

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

• Lecture 20: 3/29/2018, Covering skew-supermodular functions, iterated rounding approach of Jain.

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

• Lecture 21: 4/3/2018, Continue previous lecture.

• Lecture 22: 4/5/2018, Finish counting argument for Steiner network iterated rounding. Intro to graph cut and partition problems.

  • Note of Chandra and Thapanapong that has alternate proof for the counting arugment.

• Lecture 23: 4/10/2018, 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 of Chandra and Vivek on simple rounding for directed multiway cut

• Lecture 24: 4/12/2018, 1.5 approx for multiway cut via CKR relaxation.

  • Notes
  • Chapter 8 in Williamson-Shmoys book
  • Chapter 19 in Vazirani book
  • Paper on submodular multiway partition
  • Article on continuous extensions of submodular set functions

• Lecture 25: 4/17/2018, 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 26: 4/19/2018, Finish multicut, introduce sparsest cut.

• Lecture 27: 4/22/2016, Intro to metric embeddings, Sparsest cut via l_1 embeddings and tree embeddings.

  • 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.
  • Notes on tree embeddings from CMU class by Gupta and Ravi.

• Lecture 28: 4/24/2018, Intro to SDP, Max-Cut.

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

• Lecture 29: 5/1/2018, Constraint satisfaction problems (CSPs), hardness of approximation, closing thoughts.

  • Chapter 16 in Williamson-Shmoys book.
  • Chapters 16, 29 in Vazirani book.
  • Canonical LP and Canonical SDP for CSPs : lecture notes from CMU course.