4810-1183 Approximation and Online Algorithms with Application (Spring 2019)

Tuesday 14:55 - 16:40

Sci 7 #214

Vorapong Suppakitpaisarn
Affiliation: International Center for Information Science and Technology, Graduate School of Information Science and Technology
Office: Chemistry East Building #137 Map
E-mail: vorapong@is.s.u-tokyo.ac.jp

Quiz 30% on May 28th
Final Exam 70% on July 16th
Please send me an e-mail before April 23rd, if you are not available on any of the days.

1) David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2010.
2) A. Fiat and G. J. Woeginer (editors). Online Algorithms: The State of the Art. Springer, 1998.

Date Content Handout
4/9 Course Overview, Optimization Models, Linear Programming
4/16 NP-Hardness
4/23 Approximation Algorithms: Knapsack Problem
4/30 No Class (Golden Week)
5/7 Approximation Algorithms: Bloom Filter
5/14 Approximation Algorithms: Vertex Cover Problem
5/21 Approximation Algorithms: Set Cover Problem
5/28 Midterm Examination
6/4 No Class (Graduate School of IST will implement Friday's courses on this day)
6/11 Inapproximability
6/18 Online Algorithms: Basic Definitions
6/25 Online Algorithms: Online Learning Algorithm
7/2 Online Algorithms: Online Graph Algorithm
7/9 Guest Lecture : Prof. Evripidis Bampis (Sorbonne University)
7/16 Final Examinations