2023/10/04 Homework 1 announced (Due: 2023/11/08)
2023/11/01 Homework 2 announced (Due: 2023/11/15)
2023/12/09 Homework 3 announced (Due: 2023/12/30)
2023/10/25 Midterm exam
2023/12/20 Final exam
Lectured by Hung-Lung Wang (王弘倫)
Email: hlwang@ntnu.edu.tw
Course: Advanced Algorithms
Semester: 112-1
Credit: 3
Time: Wed. 9:10-12:10
Classroom: 理圖001
Midterm 40%
Final 40%
Participation 20%
There will be homework assignments. Submissions are optional. (You may need the credit if you don't get enough points in the exams.)
What covered in the exam:
Materials discussed in class
Homework assignments
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: 2023/09/13) NP-hardness, NP optimization problems, and approximation algorithms
Slide_02 (last update: 2023/09/27) Combinatorial approximation algorithms
Slide_03 (last update: 2023/09/27) FPTAS
Slide_04 (last update: 2023/10/31) PTAS
Slide_05 (last update: 2023/11/29) LP-based approximation: rounding
Slide 06 (last update: 2023/11/22) LP-based approximation: the primal-dual schema
Slide 07 SDP-based approximation