MS&E 319: Approximation Algorithms Administrative Information · Instructor: Amin Saberi · Lecture: Monday, Wednesday 2:45-4:00 in Terman 453 · Office Hours: Tuesday, Thursday 3:30-5:00 or by appointment · Text Book: Approximation Algorithms by Vijay Vazirani Course Objective NP-hard Optimization problems exhibit a rich set of possibilities, all the way from allowing approximability to any required degree, to essentially not allowing approximability at all. Despite this diversity, underlying the process of design of approximation algorithms are some common principles. We will explore these in this class. Outline A. Combinatorial Algorithms 1. Set Cover and Vertex Cover 2. Shortest Superstring 3. Steiner Tree and TSP 4. Multiway Cut and k-Cut 5. Polynomial-time Approximation Schemes (2-lectures) Knapsack, Bin Packing, Minimum Makespan Scheduling B. LP-Based Algorithms 6. Primal-dual algorithms for set cover and vertex cover 7. Set cover via dual-fitting 8. Rounding applied to Set Cover and Maximum Satisfiability 9. Scheduling on Unrelated Parallel Machines 10. Multiway Cut and Sparsest Cut 11. Steiner Forest 12. Primal-dual algorithms for Facility Location 13. Greedy algorithms for k-median 14. Semidefinite programming Homeworks Homework 1: solve homework 2.6, 2.15, 3.5, 3.6, 4.3, 9.9, 10.1 from the text book. Turn in only the ones in bold. Homework 2: solve 12.8, 13.6, 16.7, 19.14, 20.15, 20.16, 21.31, 22.11, 22.12, 26.12, 26.13