|
CS 583: Approximation Algorithms, Fall 2021
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 12.30-1.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 non-theory 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 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
- 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 (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
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 Williamson-Shmoys 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 Williamson-Shmoys 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 Williamson-Shmoys 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 Williamson-Shmoys 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 Lau-Ravi-Singh
- Lecture 10: 9/23/21, Congestion minimization in networks
- Chapter 7 in working notes
- Section 5.11 in Williamson-Shmoys 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 Williamson-Shmoys book
- Lecture 12: 9/30/21, Clustering and Facility Location
- Chapter 9 in working notes
- 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: 10/05/21, Primal-Dual intro and Jain-Vazirani algorithm for Facility Location
- Chapter 9 in working notes
- Chapter 24 in Vazirani book on facility location
- Chapter 7 in Williamson-Shmoys book for intro to primal-dual and several examples
- Lecture notes on facility location from CMU course
- Lecture 14: 10/07/21, Finish Jain-Vazirani algorithm for Facility Location
- Lecture 15: 10/12/21, Local Search for k-Median
- Chapter 9 in working notes
- Lecture notes on facility location from CMU course
- Chapter 9 in Williamson-Shmoys book
- Lecture 16: 10/14/21, Start network design, Steiner Tree, TSP
- Chapter 10 in working notes
- Lecture 17: 10/19/21, ATSP, Primal-Dual for Steiner Forest
- Chapter 10/11 in working notes
- Chapter 7 in Williamson-Shmoys book on primal-dual
- Goemans-Williamson survey on primal-dual for network design
- Chapter 22 in Vazirani book on Steiner Forest
- Gupta-Konemann 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
- Goemans-Williamson 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 Williamson-Shmoys book
- Lecture 24: 11/16/21, Multicut via CKR rounding and lower bound via expanders
- Chapter 16 in working notes
- Chapter 8 in Williamson-Shmoys 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 Williamson-Shmoys 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 Williamson-Shmoys 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 Max-Cut
- Chapter 6 in Williamson-Shmoys book.
- Chapter 26 in Vazirani book.
- Notes from 2006.
|
