13
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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, 2011 at 13:35
  • $\begingroup$ Links added. The FOCS paper is not yet available at this point. $\endgroup$
    – mee
    Aug 29, 2011 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, 2011 at 16:03
  • $\begingroup$ The abstract of the FOCS paper is probably better than nothing. $\endgroup$
    – Tsuyoshi Ito
    Aug 30, 2011 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, 2011 at 11:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.