Гипотеза о k-серверах наконец доказана

The k-server conjecture is true

Кристиан Коестер, Элиас Кутсупиас и Марек Збысиньский доказали гипотезу о k-серверах, открытую более трёх десятилетий назад. Они показали, что алгоритм work function достигает конкурентного отношения k на любом метрическом пространстве. Доказательство использует алгебраическое представление work function в виде матрицы: значения work function выражаются через определители k столбцов, а запрос обновляет матрицу сменой базиса и заменой строк. Амортизированный анализ опирается на потенциальную функцию от большей матрицы.