Homework1 announced (due: 2022/09/28)
Bonus problem can be submitted anytime before the end of the semester.
Homework2 announced (due: 2022/10/12 2022/10/19)
Homework3 announced (due: 2022/11/09)
Homework4 announced (due: 2022/11/30)
Homework5 announced (due: 2022/12/21)
Homework6 announced (due: 2022/12/31)
Lectured by Hung-Lung Wang (王弘倫)
Email: hlwang@ntnu.edu.tw
Course: Advanced Algorithms
Semester: 111-1
Credit: 3
Time: Wed. 9:10-12:10
Classroom: B102
Exercises 90%
Participation 10%
註：平均 2 週一次作業，繳交紙本，不發還。
V. Vazirani, Approximation algorithms, Springer, 2003.
T. H. Cormen, C.L. Leiserson, R. L. Rivest, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.
D. B. West, Introduction to Graph Theory, 2nd Ed., Prentice Hall, 2001.
G. L. Nemhauser, L. A. Wolsey, Integer and Combinatorial Optimization, Wiley 1998.
Approximation algorithms
Combinatorial algorithms
LP-based approximation
Combiatorial optimization
Greedy algorithms and matroids
Primal-and-dual algorithms
Matroid intersection
(Optional) Randomized algorithms
Probabilistic method
Slide_01 (last update 2022/12/20) NP-hardness, NP optimization problems, and approximation algorithms
Slide_02 (last update 2022/10/05) Combinatorial algorithms
Slide_03 (last update 2022/10/12) FPTAS
Slide_04 (last update 2022/11/01) PTAS
Slide_05 (last update 2022/11/23) LP-based approximation: rounding
Slide 06 (last update 2022/12/21) LP-based approximation: primal-dual schema
Slide 07 (last update 2022/12/14) Matroids and greedy algorithms