Course No.:215005Y
Period:20
Credits:1
Course Category:Advanced Course
Primary Coverage:
Lecture 1. Independent System and Greedy Algorithms
Lecture 2. Submodular Functions
Lecture 3. Greedy Approximation with Nonsubmodular Potential Functions
Lecture 4. Linear Programming
Lecture 5. Combinatorial Rounding
Lecture 6. Pipage Rounding
Lecture 7. Iterated Rounding
Lecture 8. Random Rounding
Lecture 9. Primal-Dual Method
Lecture 10. Local Ratio Method
Textbook:
Textbook: Ding-Zhu Du, Ker-I Ko and Xiaodong Hu: Design and Analysis of
Approximation Algorithms (Lecture Notes)
Author:Dingzhu Du