2026/10/27 Midterm exam
2026/12/22 Final exam
Lectured by Hung-Lung Wang (王弘倫)
Course: Advanced Algorithms
Semester: 115-1
Credit: 3
Time: Tue. 9:10-12:00
Classroom: 理圖002
Prerequisite: Algorithms, Discrete math, Formal language/Automata theory
Midterm 40%
Final 40%
Participation 20%
V. Vazirani, Approximation algorithms, Springer, 2003.
T. H. Cormen, C.L. Leiserson, R. L. Rivest, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.
Approximation algorithms
Combinatorial algorithms
Polynomial-Time Approximation Scheme (PTAS)
LP-based approximation
SDP-based approximation
Selected topics
Slide_01 (last update: 2026/09/08) Reduction, NP-hardness, NP optimization problems, and approximation algorithms
Slide_02 (last update: 2026/09/15) Combinatorial approximation algorithms
FPTAS
PTAS
LP-based approximation: rounding
LP-based approximation: the primal-dual schema
SDP-based approximation