CMPUT 675
Topics in Computing Science
Winter 2022 · Approximation Algorithms
Topics
- Greedy methods and dynamic programming
- Local search and random sampling
- Linear-programming rounding and primal-dual methods
- Semidefinite programming
- Metric embeddings
- Covering and routing problems
- Knapsack and bin packing
- Facility location
- Hardness of approximation
Readings
- David Williamson and David Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
- Vijay Vazirani. Approximation Algorithms. Springer-Verlag, Berlin, 2001.
Sources
- Course catalogue ↗2026–2027
- Approximation Algorithms ↗2022
- The course explicitly says there is no required text and that it will use these two books.