Computer Science 284/484
Instructor: Daniel Stefankovic
Thursday 12:30pm-13:45pm, CSB 632.
Instructor office hours (CSB 620): Mon, Wed 4pm-5pm, or by appointment.
Textbooks (all on a 2 hour reserve in the library):
- required: Approximation Algorithms, V. Vazirani, 2004.
- recommended: The Design of Approximation Algorithms, D.Williamson, D. Shmoys, 2011
Other resources/recommended reading (most on a 2 hour reserve in the library):
- Introduction to Algorithms (3rd edition),
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
Algorithm Design, J. Kleinberg and E. Tardos, 2005.
- The Design and Analysis of Algorithms, D. Kozen,
- The Design and Analysis of Computer
Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
Algorithms, R. Johnsonbaugh, M. Schaefer, 2003.
- How to Think About Algorithms
Algorithms, J. Edmonds, 2008.
Probability and Computing: Randomized Algorithms and
Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
- Randomized Algorithms, R. Motwani, P. Raghavan,
TOPIC: Introduction to approximation algorithms
reading: Vazirani, chapters 1-11.
Jan. 19 Th - Set cover problem
Jan. 24 Tu - Metric TSP
Jan. 26 Th - Multiway cut and k-cut
Jan. 31 Tu - k-center
Feb. 2 Th - Feedback vertex set
Feb. 7 Tu - Shortest superstring
Feb. 9 Th - Knapsack
Feb. 14 Tu - Euclidean TSP
TOPIC: Linear programming based approximation algorithms
reading: Vazirani, chapters 12-26.
Feb. 16 Th - Linear programming basics I
Feb. 21 Tu - Linear programming basics II
Feb. 23 Th - Linear programming basics III
Feb. 28 Tu - Set Cover - rounding
Mar. 1 Th - Set Cover - primal dual schema
Mar. 6 Tu - Scheduling on unrelated parallel machines
Mar. 8 Th - MIDTERM
Mar. 13 Tu - SPRING BREAK
Mar. 15 Th - SPRING BREAK
Mar. 20 Tu - Multiway cut via LP
Mar. 22 Th - Multicut
Mar. 27 Tu - Metric embeddings I
Mar. 29 Th - Metric embeddings II
Apr. 3 Tu - Sparsest cut
Apr. 5 Th - Semidefinite programming
Apr. 10 Tu - Steiner forest
Apr. 12 Th - Facility location
TOPIC: Markov Chains
Apr. 17 Tu - Monte Carlo method
Apr. 19 Th - Markov chains
Apr. 24 Tu - Colorings (coupling)
Apr. 26 Th - Matchings (canonical paths)
May. 1 Tu - review
May. 9 Wednesday (comprehensive) FINAL EXAM (7:15pm, CSB 632)
for the course is the minimum of the exam grade
and the homework grade
The midterm contributes 30% to the exam grade; the final exam contributes 70% to the exam grade.
- Homework is collected on the due date, before class.
- No late homework will be accepted without instructor's
permission (a permission must be requested at least 24 hours
before the due date).
- In the final evaluation
the lowest homework score will be
- You may work with other people on the
homework, but you must each write up your solutions separately
(without any written aid). If you work with other people, indicate
who you worked with on your solution.
- All tests are closed book. No text
or notes, no scratch paper allowed.
This course follows
The University Policy on Academic Honesty