CS 583: Approximation Algorithms, Fall 2021
Course Summary
Approximation algorithms for NPhard 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 NPhard 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 12.301.45pm in Siebel Center 0216.
Recordings: MediaSpace channel
Instructor: Chandra Chekuri, 3228 Siebel Center, (chekuri at)
Teaching Assistant: Vasilis Livanos, (livanos3 at)
Office Hours (Chandra): Tuesday, 3.30  4.30pm (virtual on Zoom). For in person make an appointment via email.
Office Hours (Vasilis): Wednesday, 4pm  5pm at the Theory Lounge (open area located between 3232 and 3304).
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 473 or equivalent. Knowledge and exposure to probability and linear programming is necessary. The instructor will try to make the material accessible to nontheory students who might be interested in applications. Consult the instructor if you have questions.
Study material:
 Recommended text books
 Chandra's working notes
 Another useful book: Approximation Algorithms for NPhard 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 HarPeled, American Mathematical Society, 2011
 A compendium of NP Optimization Problems
 Notes and slides from previous editions of the course: Spring 2018, Spring 2016, Fall 2013, Spring 2011, Spring 2009 and Fall 2006.
 Books on related topics: Combinatorial Optimization (Schrijver), Randomized Algorithms (MotwaniRaghavan), The Probabilistic Method (AlonSpencer)
 Lecture notes from various places: CMU (GuptaRavi), 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
Homework
 Homework 0 (tex file) given on 08/24/2021, due on Thursday 09/02/2021.
 Homework 1 given on 09/04/2021, due on Thursday, 9/16/2021
 Homework 2 given on 09/16/2021, due on Thursday, 9/30/2021
 Homework 3 given on 10/05/21, due on Tuesday, 10/19/2021
 Homework 4 given on 10/21/21, due on Thursday, 11/04/2021
 Homework 5 given on 11/09/21, due on Tuesday, 11/30/2021
 Homework 6 given on 11/30/21, due on Thursday, 12/09/2021
Lectures
 Lecture 1: 8/24/2021, Introduction, Covering problems, Greedy for Set Cover
 Chapters 1 and 2 in working notes
 Chapter 1 in WilliamsonShmoys book
 Chapters 1, 2 in Vazirani book
 Lecture 2: 8/26/2021, LP based algorithms for Vertex Cover/Set Cover
 Lecture 3: 8/31/2021, Set Cover: randomized rounding + alteration, dual fitting. Submodularity
 Lecture 4: 9/02/2021, Knapsack: Greedy, PTAS, FPTAS
 Chapter 3 in working notes
 Chapter 3 in WilliamsonShmoys book
 Chapter 8 in Vazirani book
 Lecture 5: 9/07/21, Maximum (Weight) Independent Set
 Chapter 4 in working notes
 Lecture 6: 9/09/21, Rectangle Independent Set, Rounding plus Alteration, Packing Integer Programs
 Chapter 4 in working notes
 Lecture 7: 9/14/21, Load Balancing, Bin Packing
 Chapter 5 in working notes
 Sections 2.3, 3.2 and 3.3, in WilliamsonShmoys book
 Chapters 9, 10 in Vazirani book
 Lecture 8: 9/16/21, Unrelated Machine Scheduling, Generalized Assignment
 Chapter 17 in Vazirani book
 Exercise 11.1 in WilliamsonShmoys book
 Chapter 6 in working notes and rank lemma in the appendix.
 Lecture 9: 9/21/21, Generalized Assignment (online lecture, scribbles)
 Section 6.2 in working notes
 Section 3.2 in iterated rounding book of LauRaviSingh
 Lecture 10: 9/23/21, Congestion minimization in networks
 Chapter 7 in working notes
 Section 5.11 in WilliamsonShmoys book
 Lecture 11: 9/28/21, Introduction to Local Search via Max Cut and Submod Maximization
 Chapter 8 in working notes
 Parts of Chapters 2 and 9 in WilliamsonShmoys book
 Lecture 12: 9/30/21, Clustering and Facility Location
 Chapter 9 in working notes
 Chapter 2 in WilliamsonShmoys book for kcenter (Gonzalez's algorithm)
 Chapter 5 in Vazirani book for kcenter (the bottleneck algorithm)
 Lecture 13: 10/05/21, PrimalDual intro and JainVazirani algorithm for Facility Location
 Chapter 9 in working notes
 Chapter 24 in Vazirani book on facility location
 Chapter 7 in WilliamsonShmoys book for intro to primaldual and several examples
 Lecture notes on facility location from CMU course
 Lecture 14: 10/07/21, Finish JainVazirani algorithm for Facility Location
 Lecture 15: 10/12/21, Local Search for kMedian
 Chapter 9 in working notes
 Lecture notes on facility location from CMU course
 Chapter 9 in WilliamsonShmoys book
 Lecture 16: 10/14/21, Start network design, Steiner Tree, TSP
 Chapter 10 in working notes
 Lecture 17: 10/19/21, ATSP, PrimalDual for Steiner Forest
 Chapter 10/11 in working notes
 Chapter 7 in WilliamsonShmoys book on primaldual
 GoemansWilliamson survey on primaldual for network design
 Chapter 22 in Vazirani book on Steiner Forest
 GuptaKonemann survey on network design
 Lecture 18: 10/21/21 Finish Steiner Forest
 Lectures 19 and 20: 10/26/21 and 10/28/21. Primal dual for uncrossable functions and applications
 Chapter 12 in working notes
 GoemansWilliamson survey
 Lecture 21: 11/02/21 Iterated Rounding for Survivable Network Design
 Chapter 13 in working notes
 Chapter 23 in Vazirani book
 Chapter 11 in Williamson Shmoys book
 Lecture 22: 11/04/21 Finish counting argument for SNDP iterated rounding
 11/09/21: no lecture
 Lecure 23: 11/11/21, Introduction to cuts/metrics, Multiway Cut
 Chapter 15 in working notes
 Chapter 19 in Vazirani book
 Chapter 8 in WilliamsonShmoys book
 Lecture 24: 11/16/21, Multicut via CKR rounding and lower bound via expanders
 Chapter 16 in working notes
 Chapter 8 in WilliamsonShmoys book
 Chapters 18 and 20 in Vazirani book
 Lecture 25: 11/18/21, Sparsest Cut
 Chapter 17 in working notes
 Chapter 21 in Vazirani book
 Chapter 15 in WilliamsonShmoys book.
 Lecture notes on metric embeddings by Matousek. Also a chapter on emebdding finite metric spaces in normed spaces.
 Lecture 26: 11/30/21, Tree Embeddings
 Notes from CMU
 Chapter 8 in WilliamsonShmoys book. Do you know what the picture on the cover of the book represents?
 Old slide notes of Chandra with O(log^2 n) bound
 Lecture 27: 12/2/21, SDP and MaxCut
 Chapter 6 in WilliamsonShmoys book.
 Chapter 26 in Vazirani book.
 Notes from 2006.
