Recently the long-standing k-server problem has been solved by Nikhil Bansal, Niv Buchbinder, Aleksander Mądry 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_problem

adwords: http://www.stanford.edu/~saberi/adwords.pdf

  • 2
    $\begingroup$ Could you at least state the k-server and/or the adwords problems? In that way, those of us who are not familiar with the area can get an idea of what you are talking about. $\endgroup$ – Janoma Aug 29 '11 at 13:35
  • $\begingroup$ Links added. The FOCS paper is not yet available at this point. $\endgroup$ – mee Aug 29 '11 at 13:56
  • 9
    $\begingroup$ The FOCs paper doesn't "solve" the conjecture technically, since the conjecture asks for a log k competitive randomized strategy. It comes much closer though, since it is o(k). $\endgroup$ – Suresh Venkat Aug 29 '11 at 16:03
  • $\begingroup$ The abstract of the FOCS paper is probably better than nothing. $\endgroup$ – Tsuyoshi Ito Aug 30 '11 at 0:54
  • $\begingroup$ Would stochastic programming fall under this category? (such as in updating option prices as soon as new data comes in) $\endgroup$ – v s Aug 31 '11 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.