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:
-
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.
| |