4810-1185 Network Optimizations (Autumn 2018)

Announcement : There will be a midterm and final examination on November 12th and January 7th from 14:55 at Sci. 7 102. Please drop me an e-mail if you cannot attend the exam.

Date/Time : Monday 14:55 - 16:40

Place : Sci 7 #102

Instructor : Vorapong Suppakitpaisarn
(Chemistry Building #137, vorapong@is.s.u-tokyo.ac.jp)

Evaluation : Midterm Exam 30% Final Exam 70%

Course Website: http://www.vorapong-sup.net/NetOpt2018.html
(Please replace 2018 with 2017 and 2016 to find the course website on the previous
iteration. You can find the previous exam questions there.)

Material :

1) Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson, 2005.
2) Ding-Zhu Du and Peng-Jun Wan. Connected Dominating Set: Theory and Applications. Springer, 2012.
3) Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. Mining of Massive Datasets. Cambridge University Press, 2014.

Schedule :

Date

Content

10/1

Course Overview, Quick Review on Approximation Algorithms Note

10/8

No Class (public holiday)

10/15

Social Networks: Network Clustering Note

10/22

Social Networks: Algorithms for PageRank and SimRank Note

10/29

Social Networks: Algorithms for PageRank and SimRank (cont.)

11/5

Social Networks: Influence Maximization

11/8 (Thu)

Social Networks: Influence Maximization (cont.)

11/12

Midterm Examination

11/19

Sensor Networks: Minimum Weight Target Coverage Problem

11/26

Sensor Networks: Maximum Lifetime Coverage Problem

12/3

Sensor Networks: Maximum Lifetime Coverage Problem (cont.)

12/10

Sensor Networks: Localization Problem

12/18

Guest Lecture (TBD)

12/24 and 12/31

No Class

1/7

Final Examination

Material for Class 1 :

1) For basic definitions of graphs and trees, please refer to Chapter 3.1 3.2 the following book.
Jon Kleinberg and Eva Tardos. Algorithm Design . Pearson, 2005.
2) Definitions of social networks can be found at Chapter 10.1 of the following book.
Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. Mining of Massive Datasets. Cambridge University Press, 2014.