2 problems

0 votes0 replies0 views
The deterministic $k$ -server conjecture
The deterministic $k$ -server conjecture. There exists a deterministic online algorithm for the $k$ -server problem with competitive ratio $k$ .
Conjectureopencompetitive-analysis k-server-problem online-algorithmsarXiv posted 2 days ago
0 votes0 replies0 views
The randomized $k$ -server conjecture
Let $\mathsf{R}_k(X)$ denote the infimum of competitive ratios achievable by randomized online algorithms for the $k$ -server problem on a metric space $X$ . The randomized $k$ -serve…
Conjectureopenk-server-problem online-algorithms randomized-algorithmsarXiv posted 2 days ago

The deterministic kkk-server conjecture