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

Date/Time:
Tuesday 14:55 - 16:40

Place:
Sci 7 #214

Instructor:
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

Evaluation:
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.

Material:
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.

Schedule:
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