수십 년 난제 'k-서버 추측' 마침내 증명
Key Point
온라인 알고리즘 이론에서 장기간 미해결이었던 핵심 추측의 증명으로, 경쟁적 분석 분야의 기초를 정립하는 중요한 진전이다.
핵심 요약
- 알고리즘 이론의 난제인 k-서버 추측이 증명됐다. 결정론적 온라인 알고리즘이 모든 메트릭 공간에서 경쟁비 k를 달성할 수 있다는 내용이다.
- 증명에는 일함수(work function) 알고리즘이 사용됐다. 이를 행렬의 대수적 표현으로 변환해 모든 가능한 경로를 인코딩한다.
- 행렬 표현에서 최솟값과 덧셈 연산이 형식식의 덧셈과 곱셈에 대응되며, 각 일함수 값은 행렬의 k개 열의 행렬식과 같다.