Before revision:  Previously, the only known solution for this problem with a sub-linear competitive ratio was randomized Alon et al. , TALG 2006].
After revision:  Previously, the only known solution for this problem with a sub-linear competitive ratio was randomized Alon et al. TALG 2006].