CSCI 2950-w - Online Algorithms - Fall 2009

CSCI 2950-w - Online Algorithms

Announcement

Lectures will be in 367. That room holds 34 people in theory, and this is a Theory course.
9/9: Looking for pair of volunteers for completing the wikipedia page on page replacement algorithms.

When, where, who

Instructor:  Claire Mathieu (claire at cs.brown.edu), CIT 555, x36066
Lecture Location and Time:  CIT 367, WF 10:30 - 11:50 am
Office hours:  W 1-2pm and by appointment.
Prerequisites:  CS157 or equivalent. This is a good course for senior undergraduates who have enjoyed CS 157 and want to go beyond that, and for graduate students who want a Theory course.
Bibliography: 
Online Algorithms and Competitive Analysis, Alan Borodin and Ran El-Yaniv, Cambridge University Press; Online Computation, Sandy Irani and Anna Karlin, chapter 13 of the book "Approximation Algorithms for NP-hard Problems" edited by Dorit S. Hochbaum; Data Streams: Algorithms and Applications, Muthu Muthukrishnan's lecture notes. Online Algorithms chapter by Suzanne Albers

What

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.

Evaluation

As they come up, solve a few exercises/problems and present them in class. Towards the end of the semester, read and present a paper. Help create some wikipedia pages on online algorithms.

Schedule

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


Papers

  • Online bipartite matching made simple (David E., Sunil)
  • Online Stochastic Matching: Beating 1-1/e, Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan. IEEE FOCS 2009.
  • Online conflict-free coloring for intervals Amos Fiat,Meital Levy,Jirí Matou?ek,Elchanan Mossel,Janos Pach,Micha Sharir,Shakhar Smorodinsky,Uli Wagner,Emo Welzl, ACM SIAM SODA 2005 (Aaron, Sasha)
  • Scheduling parallel machines online Shmoys Wein Williamson (Matteo, Andrew)
  • SRPT is 1.86-Competitive for Completion Time Scheduling, Christine Chung, Tim Nonner, Alexander Souza. ACM SIAM SODA 2010.
  • Approximating the minimum spanning tree weight in sublinear time (Adrian, Sid)
  • Online facility location (David, Steven)
  • Clustering data streams (Olya, Foteini)
  • Randomized online algorithms for minimum metric bipartite matching (Rebecca, Erik)
  • A 1.4-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model. Bahman Bahmani, Aranyak Mehta, Rajeev Motwani. ACM SIAM SODA 2010.
  • A multiple-choice secretary algorithm with applications to online auctions, Robert Kleinberg, ACM SIAM SODA 2005 (or the related, more recent paper on the Hiring problem by Upfal et al)
  • S. Albers and Hiroshi Fujiwara. Energy-efficient algorithms for flow time minimization. In Proc. 23rd International Symposium on Theoretical Aspects of Computer Science (STACS'06), Springer LNCS 3884, 621-633, 2006.
  • Multi-armed bandit problems in metric spaces Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC 2008), 681-690.
  • A Primal-Dual Randomized Algorithm for Weighted Paging Nikhil Bansal, Niv Buchbinder and Seffi Naor, 48th annual ieee Symposium on Foundations of Computer Science (FOCS 2007)
  • Online Ad Slotting With Cancellations Authors: Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pal, SODA 2009