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

Announcement:
May 30th (quiz date) is actually a day that IST will use Friday's schedule.
We will have a quiz at Chemistry Building #236 (which is different from our classroom)
If you cannot take the quiz on May 30th, you can also take the quiz on June 13th.
The problem set on May 30th and June 13th will be different.

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 Building #137 Map
E-mail: vorapong@is.s.u-tokyo.ac.jp

Evaluation:
Quiz 30% on May 30th
Final Exam 70% on July 11th
Please send me an e-mail before April 19th, 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 Notes Bonus
4/11 Course Overview, Optimization Models, Linear Programming Download Download 48-179714
4/18 NP-Hardness Download Download 48-176444
4/25 Approximation Algorithms: Knapsack Problem Download Download
5/2 Approximation Algorithms: Bloom Filter Download Download 48-165104, 48-166637, 48-176126, 48-176229
5/9 Approximation Algorithms: Vertex Cover Problem Download Download 37-165104
5/16 No Class
5/23 Approximation Algorithms: Clustering Problems Download Download
5/30 Quiz on Approximation Algorithms Download
6/6 Inapproximability Download Download
6/13 Quiz on Approximation Algorithms (for those who cannot join the quiz on 5/30) Download
6/20 Online Algorithms: Basic Definitions Download Download 48-176229
6/27 Online Algorithms: Basic Definitions (cont.) Download Download 48-176126
7/4 Online Algorithms: Online Learning Algorithm Download Download, Mock-up Exam
7/11 Final Examination Download
7/18 Questions & Answers