La conjetura de los k-servidores es cierta

The k-server conjecture is true

Christian Coester, Elias Koutsoupias y Marek Zbysiński demuestran la conjetura de los k-servidores: existe un algoritmo online determinista con ratio competitivo k en cualquier espacio métrico. La prueba muestra que el work function algorithm la satisface, usando una representación algebraica de la work function como matriz cuyas entradas codifican todos los caminos factibles, y un análisis amortizado basado en una función potencial.