3 problems

Randomized metrical task systems conjecture. The asymptotically tight $\Theta(\log n)$ competitive-ratio bound holds in all metric spaces.

Logarithmic competitive-ratio conjecture. The competitive ratio for metrical task systems on every $n$-point metric space is

Let $(X,d_X)$ be a finite metric space with $|X|=n>1$. In the metrical task systems problem, an online algorithm receives a sequence of nonnegative service-cost functions…