CS590: Approximation Algorithms
Text Book
None of the book is required. Following books are recommended.
Course Description
Many important optimization problems are NP-hard to solve exactly. On the other hand, it is, in many cases, easy to find solutions that are guaranteed to be close to the optimum. Formally speaking, an alpha-approximation algorithm finds a solution that is within an alpha factor of the optimal solution. In the first half of the course, we will give a broad introduction on various methods on designing approximation algorithms for fundamental problems. In the second half of the course, we will focus on more advanced and specialized topics.
Topics
Schedule
(1/8) -- No Class
(1/10) -- Introduction, vertex Cover ([WS] Chap 1)
(1/15) -- Set Cover ([WS] Chap 1)
(1/17) -- Max Coverage and Scheduling ([WS] Chap 2.3, proof for the max coverage problem)
(1/21) -- Maximizing a monotone submodular function, 2 approximation for metric TSP ([WS] Chap 2.4, 2.5,Jan's note on submodular functions)
(1/23) -- 1.5 approximation for metric TSP, k center ([WS] Chap 2.4, 2.2 Chandra's note on mincost perfect matching)
(1/28) -- Knapsack, Bin Packing ([WS] Chap 3.1,3.3, shuchi's notes)
(1/30) -- Minimizing sum of completion times, Separation oracle ([WS] Chap 4.1,4.2,4.3,Mitchell's notes on ellipsoid algorithm)
(2/5) -- Sepration Oracle, Prize Collecting for Steiner Trees ([WS] Chap 4.3,4.4,
2-Approximation for the Steiner Tree )
(2/7) -- LP duality (Appendix A, LP Duality, note on vertex cover)
(2/12) --Vertex Cover,Steiner Tree (note on steiner Tree)
(2/14) --Facility Location
(2/19) --Randomized Rounding ([WS] Chap 5.1,5.7)
(2/21) --Randomized Rounding ([WS] Chap 5.2-5.5)
(2/26) --Randomized Rounding ([WS] Chap 5.6-5.8)
(2/28) --Randomized Rounding ([WS] Chap 5.9-5.12, notes on Chernoff Bound)
(3/5) -- Semidefinite Programming ([WS] Chap 6.1, 6.2)
(3/7) --Semidefinite Programming ([WS] Chap 6.4)
(3/12)-- Spring Break
(3/14) --Spring Break
(3/19)-- Semidefinite Programming([WS] Chap 6.3,6.5)
(3/21) --Primal Dual (1)
(3/26) --Primal Dual (2)
(3/28) -- Cut and Metrics (1)
(4/2) -- Cut and Metrics (2)
(4/4) -- Cut and Metrics (3)
(4/9) -- Chap 8.3, student presentation (Sital, Chap 2.6)
(4/11) -- student presentation (Vaishnavi, Pablo, Influnece maximization)
(4/16) -- stduent presentation (Qifan, Yao(paper 1,paper 2))
(4/18) -- student presentation (Nader(betweenness), Adnan(pdf))
(4/23) -- student presentation (Leo,Nabeel pdf)
(4/25) -- Inapproximability (pdf)