Analysis and Design of Approximation Algorithms

  • 申立勇
  • Created: 2014-12-08
Analysis and Design of Approximation Algorithms


Course No.215005Y   



Course CategoryAdvanced 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: Ding-Zhu Du, Ker-I Ko and Xiaodong Hu: Design and Analysis of
Approximation Algorithms (Lecture Notes)

AuthorDingzhu Du