4810-1183 Approximation and Online Algorithms with Application (Spring
2019)
Date/Time:
Tuesday 14:55 - 16:40
Place:
Sci 7 #007 We have changed the classroom
Instructor:
Vorapong Suppakitpaisarn
Affiliation
: International Center for Information Science and Technology, Graduate
School of Information Science and Technology
Office
: Chemistry East Building #137
The building is next to Sci. 7. You can get to my office by using the
lobby exit of Sci. 7, cross the bicycle parking, and enter the next
building. My office is the first room after you enter the building.
E-mail
: vorapong@is.s.u-tokyo.ac.jp
Office Hour
: Thursday 4 pm 5:30 pm
Please drop me an e-mail if you want to meet at other date/time.
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.
Course Website
:
www.vorapong-sup.net/AO2019.html
Please refer to the website for the previous iteration at
www.vorapong-sup.net/AO2018.html
and
www.vorapong-sup.net/AO2017.html
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 |
Note LP Files Display Files Update: I have missed the "display file" in the note distributed at the class. |
|
4/16 |
NP-Hardness |
Note |
|
4/23 |
Approximation Algorithms: Knapsack Problem |
Note |
|
4/30 |
No Class (Golden Week) |
|
|
5/7 |
No Class (Business Trip) |
|
|
5/14 |
Approximation Algorithms: Bloom Filter |
Keys to Exercises |
|
5/21 |
Approximation Algorithms: Vertex Cover Problem |
Note |
|
5/28 |
Midterm Examination |
Questions
|
|
6/4 (10:25 - 12:10) @ 214 |
Approximation Algorithms: Set Cover Problem
|
Note |
|
6/11 |
Inapproximability |
Note |
|
6/18 |
Guest Lecture : Prof. Evripidis Bampis (Sorbonne University) |
Materials (Chapter 0.1 to 0.4) |
|
6/25 |
Online Algorithms: Ski Rental Problem |
Note |
|
7/2 |
Online Algorithms: Secretary Problem |
Note |
|
7/9 |
Online Algorithms: Online Machine Learning Algorithm |
Note |
|
7/16 |
Final Examinations |