CS49/149: Approximation Algorithms, Spring 2017
Instructor: Deeparnab Chakrabarty (Office hours: Wed 3:30pm - 5pm, or by appointment @Sudikoff 216)
Time: 10A (TR: 10:10am - 12noon)
Venue: Sudikoff 214
Many problems arising in computer science are NP-hard and we do not expect polynomial time
algorithms solving them exactly. This has led to the study of approximation algorithms where one relaxes
the goal to return approximate solutions. Over the past three decades, a beautiful theory of approximation
algorithms has emerged. This course provides a broad overview of the main techniques in the area.
A first course on algorithms and the ability to read and write mathematical proofs will be required.
Prerequisite course: CS 31 or equivalent. Desirable: CS 30, CS 231.
There is no required textbook but the following books are highly recommended.
- The Design of Approximation Algorithms by David Williamson and David Shmoys. (pdf) .
- Approximation Algorithms by Vijay Vazirani. (pdf)
Assignments (70%), Endterm or Project (30%)
Each week will be devoted to one or two techniques illustrated on a few problems.
- Week 1: Introduction, Greedy Algorithms, Local Search Algorithms.
- Week 2: Approximation Schemes
- Week 3: Linear Programming Relaxations
- Week 4: Deterministic Rounding
- Week 5: Iterated Rounding
- Week 6: Randomized Rounding
- Week 7: Primal-Dual Methods
- Week 8: Semidefinite Programming Relaxations
- Week 9: Inapproximability
There will be weekly assignments with 3-4 problems which will serve as a revision and reinforcement for the material covered in class.
Students are highly encouraged to start early. Each point will be worth 7 points and we
will follow Amit Chakrabarti's excellent and detailed grading policy..
Please refer to the "Working Together and Honor Priniciple" in the same page as well.