CS49/149: Approximation Algorithms, Spring 2017
Instructor: Deeparnab Chakrabarty (Office hours: T,R: 1:30pm - 2:30pm, or by appointment @Sudikoff 216)
Time: 10A (TR: 10:10am - 12noon)
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 and the ability to read and write mathematical proofs will be required.
Prerequisite course: CS 31 or equivalent. Desirable: CS 30, CS 231.
Recommended Books
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)
Evaluation
Assignments (70%), Endterm (30%)
Assignments
We will use Canvas for the submitting and grading assignments.
Grading
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.
Lectures
These lecture notes are very rough drafts of what I plan to cover. Often I would either cover less or cover more.
Please email me if there are errors or somthing is unclear.
- Introduction: Definition, Maximal Matching, TSP. (pdf)
- Greedy algorithms: Set cover, Max-coverage (pdf)
- Local Search: Max-Coverage, k-Median. (pdf)
- PTAS: P||Cmax. (pdf)
- Linear Programming Relaxationas. (pdf) Some notes on LPs (pdf)
- Deterministic Rounding: facility location, bipartite matching, unrelated machine scheduling. (pdf)
- Rank Arguments: bipartite perfect matching, unrelated machine scheduling, tree augmentation. (pdf)
- Rank Arguments: discrepancy of set systems (the Beck-Fiala theorem). (pdf)
- Rank Arguments: minimum spanning tree polytope. (pdf)
- Ellipsoid algorithm: solving LPs with exponentially many constraints. (pdf)
- The Dual: Introduction, Proof of Strong Duality, Vertex Cover Primal-Dual algo. (pdf)
- The Dual: Primal-Dual algorithm for Facility Location. (pdf)
- Randomized Rounding: Set Cover, Independent Set. (pdf)
- Randomized Rounding: Chernoff Bounds, Discrepancy of Set Systems, Congestion Minimization. (pdf)
- Cut Problems: s,t min-cut, Multiway Cut, Multicut. (pdf)
- Cut Problems: Uniform Sparsest Cut. (pdf)
- Semidefinite Programming: Max-Cut. (pdf)
- Semidefinite Programming: Independent Sets in 3-colorable Graphs. (pdf)