Recently the long-standing k-server problem has been solved by Nikhil Bansal, Niv Buchbinder, Aleksander Mdry and Seffi Naor (to appear in FOCS 2011). I'm interested in knowing other open problems in online algorithms. Of course it's impossible to list all of them so I'm primarily looking for the more important/famous/notorious ones.e.g. the k-server problem would be a good one, so is the adwords problem (which has received considerable attention recently).Some background:k-server: http://en.wikipedia.org/wiki/K-server_problemadwords: http://www.stanford.edu/~saberi/adwords.pdf
Online algorithms: open problems
ds.algorithms;reference request;open problem