Decisions must often be made before the entire data is available. Online algorithms solve problems in which commitments must be made as the data is arriving. Choosing which items to evict from a cache before knowing future requests, which advertisers to consider for displaying ads alongside the result of a search, or which most representative data to store when computing statistics about a huge stream of information. We will discuss worst-case model, which hinges against the worst possible future data, and some stochastic and game-theoretic models.
This graduate course focuses on the design and analysis of algorithms when the data is not all available at first. The course will be structured partly around reading a few selected chapters of the Borodin-El Yaniv textbook, the Irani-Karlin survey, and Muthukrishnan's lecture notes, and partly (towards the end of the semester) around reading and presenting papers on recent research. Each paper is read by a pair of students.
Date | Topic |
Notes |
Sept 9 |
Deterministic Paging |
Due 9/11: LRU no better than k-competitive; LIFO and LFU not competitive |
Sept 11 |
Randomized Paging |
|
Sept 16 |
Lower bounds |
|
Sept 18 |
Primal-dual weighted paging |
Due 9/25: Marking is not Hk competitive; Marking is Hk competitive when the universe has size k+1. |
Sept 23 |
Weighted paging |
|
Sept 25 |
Weighted paging (cont'd), ski rental, ad auctions algorithm |
Survey Buchbinder-Naor |
Monday, Sept 28 |
||
Sept 30 |
Optimality of LRU in tree access graphs |
notes |
Oct 2 |
No class, replaced by Sept 28 |
|
Oct 7 |
Dynamic optimality conjecture; online bribery |
online bribery |
Oct 9 |
||
Oct 14 |
||
Oct 16 |
||
Oct 21 |
||
Oc 23 |
k server |
notes |
Oct 28 |
||
Oct 30 |
streaming, test |
solution |
Nov 4 |
||
Nov 6 |
||
Nov 11 |
||
Nov 13 |
||
Nov 18 |
||
Nov 20 |
Olya and Foteini, Matteo and Andrew, David E and Sunil |
|
Monday, Nov 23 |
Adrian and Sid, Aaron and Sasha, Rebecca and Erik |
|
Nov 25 |
No class, replaced by Nov 23 |
|
Nov 27 |
No class, Thanksgiving weekend |
|
Dec 2 |
David Li and Steven |
|
Dec 4 |