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

5/21

Approximation Algorithms: Vertex Cover Problem

Note

5/28

Midterm Examination

6/4 (10:25 - 12:10) @ 214

Approximation Algorithms: Set Cover Problem
Note: 6/4 afternoon will be for Friday's class.

6/11

Inapproximability

6/18

Guest Lecture : Prof. Evripidis Bampis (Sorbonne University)

6/25

Online Algorithms: Basic Definitions

7/2

Online Algorithms: Online Learning Algorithm

7/9

Online Algorithms: Online Graph Algorithm

7/16

Final Examinations