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

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

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/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