k-server 추측, 마침내 증명되다
The k-server conjecture is true
Christian Coester, Elias Koutsoupias, Marek Zbysiński가 모든 metric space에서 deterministic online algorithm이 경쟁비 k를 달성할 수 있다는 k-server 추측을 증명했다. 이들은 work function algorithm이 이를 만족함을 보였으며, work function을 행렬로 표현해 최적 비용의 최솟값과 덧셈 연산을 형식적 표현의 덧셈과 곱셈으로, 각 work function 값을 행렬 k개 열의 determinant로 대응시켰다. 요청 도착은 기저 변환과 행 교체로 표현을 갱신하고, amortized analysis는 원래 행렬 좌표 쌍을 좌표로 하는 더 큰 행렬의 potential function에 기반한다.
The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space. We prove the conjecture.