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

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 June 5th
Final Exam 70% on July 17th
Please send me an e-mail before April 24th, 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/10 Course Overview, Optimization Models, Linear Programming Syllabus, Handout
4/17 NP-Hardness Handout
4/24 Approximation Algorithms: Knapsack Problem Handout
5/1 No Class (Golden Week)
5/8 Approximation Algorithms: Bloom Filter Handout
5/15 Approximation Algorithms: Vertex Cover Problem Handout
5/22 Approximation Algorithms: Set Cover Problem No Handout
5/29 No Class (Graduate School of IST will implement Friday's courses on this day)
6/5 Midterm Examination Problems
6/12 Inapproximability Handout
6/19 Online Algorithms: Basic Definitions Handout
6/25 Online Algorithms: Online Learning Algorithm Handout
7/3 Online Algorithms: Online Graph Algorithm No Handout
7/10 Guest Lecture : Dr. Chien-Chung Huang (ENS)
7/17 Final Examinations Problems