Prerequisites

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.

• LP duality. For a quick refresher, see Lecture notes by Shuchi Chawla or by Anupam Gupta .
• Chernoff bounds. See once again lecture notes by Shuchi Chawla, John Canny or Bob Tarjan.

Students are expected to scribe one of the lectures. There will be no exams. There will be suggested exercises, not mandatory.

Course Notes, etc.

• [Jan 9] Pictures from the board: 1 | 2 | 3 | 4 | 5 | 6     Scribe Notes
  
• [Jan 11] Pictures from the board: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8     Scribe Notes
  
• [Jan 16] Pictures from the board: 1 | 2 | 3 | 4     Scribe Notes
  
• [Jan 18] Pictures from the board: 1 | 2 | 3 | 4 | 5 | 6 | 7     Scribe Notes
  
• [Jan 23] Pictures from the board: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
  
• [Jan 25] Pictures from the board: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  
• [Jan 30] Handwritten Notes     Scribe Notes
• [Feb 1 and 6] Handwritten Notes     Scribe Notes
• [Feb 8] Handwritten Notes
• [Feb 13-15] Handwritten Notes     Scribe Notes
• [Feb 20-22] Handwritten Notes     Scribe Notes
• [Feb 22] Handwritten Notes
• [Feb 27]     Scribe Notes

Suggested Exercises

• [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.
  

Topics

The following is a (tentative) list of topics to be covered in the course.

Part 1: Online bipartite matching and its generalizations:

• Online Bipartite Matching, fractional version. Primal-Dual algorithm.
  
• Online Bipartite Matching, integral version. Randomized Primal-Dual Analysis of the RANKING Algorithm. [Devanur, Jain and Kleinberg, SODA 2013]
• The Adwords or the (fractional) online budgeted allocation problem, Primal-Dual algorithm. [ Mehta, Saberi, Vazirani and Vazirani, FOCS 2005/JACM 2007, | Buchbinder, Jain and Naor, ESA 2007]
• The Adwords problem with random arrival order, greedy algorithm. [Goel and Mehta, SODA 2008 | Devanur, Jain and Kleinberg, SODA 2013]
• Vertex weighted online bipartite matching. [Aggarwal, Goel, Karande and Mehta, SODA 2011 | Devanur, Jain and Kleinberg, SODA 2013]
• Online Ad Assignment with Free Disposal. [Feldman, Korula, Mirrokni, Muthukrishnan and Pál, WINE 2009 | Korula, Mirrokni and Yan, AAW 2012]
• Online Matching with Concave Returns. [Devanur and Jain, STOC 2012]
• Online Bipartite Matching, integral version with random arrival order. [Mahdian and Yan, STOC 2011 | Karande, Mehta and Tripathi, STOC 2011]
• The Adwords problem with random arrival order, learning based algorithm. [Devanur and Hayes, EC 2009 ]
• The general assignment problem with random arrival order, learning based algorithm. [Agarwal, Wang and Ye | Feldman, Henzinger, Korula, Mirrokni and Stein, ESA 2010]
• The online b-matching problem with i.i.d arrival. [Motwani,Panigrahi and Xu, APPROX-RANDOM 2006 ]
• The Adwords problem with i.i.d arrival, hybrid argument. [Devanur, Sivan and Azar, EC 2012 ]
• The general assignment problem problem with i.i.d arrival, hybrid argument. [Devanur, Jain, Sivan and Wilkens, EC 2011 ]
• The online submodular welfare problem with i.i.d arrival, hybrid argument. [Kapralov, Post and Vondrak, SODA 2013]
• The online bipartite matching with i.i.d arrival, known distribution. [Manshadi, Oveis Gharan and Saberi, SODA 2011]
• Open problems: integral budgeted allocation problem, integral free disposal. Impossibility of using the LP relaxation. [Kapralov, Post and Vondrak, SODA 2013]

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.