CS 583: Approximation Algorithms, Spring 2018
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.
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): TBA in 3228 Siebel
Office Hours (Vivek): TBA 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. 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.
Recommended text books
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
Homework 0 (tex file) given on 01/16/2018, due in class on Thursday 01/25/2018.
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