CS49/149: Approximation Algorithms, Fall 2019
Instructor: Deeparnab Chakrabarty (Office hours: Right after class, or by appointment @Sudikoff 216)
Time: 2A (TR: 2:25pm - 4:15pm)
Venue: Sudikoff 214
Course Description
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.
Background
A first course on algorithms. Ability to read and write mathematical proofs is required.
Prerequisite course for UGs: CS 31 or equivalent.
Recommended Books
There is no required textbooks. The following books are recommended.
- The Design of Approximation Algorithms by David Williamson and David Shmoys. (pdf) .
- Approximation Algorithms by Vijay Vazirani. (pdf)
Evaluation
Weekly Problem Set (50%), Research (50%)
- Each week, there will be a problem set due on Monday night. I will be asking you to solve two problems.
You can discuss the problems with your classmates and instructors
but you must mention who all you talked with. What you turn in must be in your own words.
-
The details on deliverables on "Research" will be posted on Canvas and discussed in class.
Assignments
- Problem set 0 (Not for submission, but you should be able to tackle these problems)
We will use Canvas for the submitting and grading assignments.
Tentative Schedule
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