<p>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.</p>

<p>e.g. the k-server problem would be a good one, so is the adwords problem (which has received considerable attention recently).</p>

<p>Some background:</p>

<p>k-server: <a href="http://en.wikipedia.org/wiki/K-server_problem">http://en.wikipedia.org/wiki/K-server_problem</a></p>

<p>adwords: <a href="http://www.stanford.edu/~saberi/adwords.pdf">http://www.stanford.edu/~saberi/adwords.pdf</a></p>

CC BY-SA 3.0
2011-08-29T13:35:52.687Z
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.
Janoma
CC BY-SA 3.0
2011-08-29T13:56:20.933Z
Links added. The FOCS paper is not yet available at this point.
mee
CC BY-SA 3.0
2011-08-29T16:03:42.103Z
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).
Suresh Venkat
CC BY-SA 3.0
2011-08-30T00:54:32.067Z
The [abstract of the FOCS paper](http://people.csail.mit.edu/madry/docs/kserver_abs.pdf) is probably better than nothing.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-31T11:25:42.327Z
Would stochastic programming fall under this category? (such as in updating option prices as soon as new data comes in)
v s
<ds.algorithms><reference-request><open-problem>
Online algorithms: open problems
mee
# Online algorithms: open problems

(Asked by: username_0 on 2011-08-29)

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>

**Tags:** ds.algorithms, reference-request, open-problem

> **Comments:**
> **username_1**: 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.  
> **username_0**: Links added. The FOCS paper is not yet available at this point.  
> **username_2**: 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).  
> **username_3**: The [abstract of the FOCS paper](http://people.csail.mit.edu/madry/docs/kserver_abs.pdf) is probably better than nothing.  
> **username_4**: Would stochastic programming fall under this category? (such as in updating option prices as soon as new data comes in)  

---

## 0 answers

