CSE 599I Online Algorithms
Winter Quarter 2013.
Instructor: Nikhil R. Devanur.
Wednesdays and Fridays 10:30-11:50 am.
Room # CSE 203.
It will be assumed that the students are familiar with the basics of the design and analysis of algorithms in addition to the following topics.
Students are expected to scribe one of the lectures. There will be no exams. There will be suggested exercises, not mandatory.
• [Jan 11] Extend the proof of the fractional bi-partite matching problem to the b-matching problem. Compare with the analysis of Kalyanasundaram and Pruhs.
• [Jan 11, more challenging] Extend the proof of the fractional bi-partite matching problem to the fractional budgeted allocation problem. Compare with the analysis of Mehta, Saberi, Vazirani and Vazirani.
• [Jan 16] Convert the proof of the fractional budgeted allocation problem to a primal-dual proof. Compare with the analysis of Mehta, Saberi, Vazirani and Vazirani.
• [Jan 16] Extend the proof of the RANKING algorithm to the vertex weighted version of online bipartite matching. Compare with the analysis of Aggarwal, Goel, Karande and Mehta.
• [Jan 18] Compare the analysis from class of the bipartite matching with free disposal problem with that of Feldman, et. al.
• [Jan 18] Compare the analysis from class of the greedy algorithm for the fractional budgeted allocation problem with random arrival order with that of Goel and Mehta.
• [Jan 25] Extend the analysis of the free disposal problem in class to the case where the constraints on the vertices in L have arbitrary non-negative coefficients.
The following is a (tentative) list of topics to be covered in the course.

Part 1: Online bipartite matching and its generalizations:
Part 2: Classics
• The ski rental problem.
• Paging, deterministic and randomized algorithms.
• Weighted paging, primal-dual algorithm.
• Load balancing: power of 2 choices.
• Learning from Experts: Multiplicative weight update method. Applications.
• The Secretary problem. Dealing with incentives.
• Online Set Cover.
• The k-server problem.
• Energy efficient online scheduling.