Алгоритм рабочей функции для k серверов: различия между версиями

Теорема 1 подходит исключительно близко к доказательству k-серверной гипотезы, описанной ранее. Была даже высказано предположение, что сам алгоритм WFA является k-конкурентными для k серверов, однако доказать его пока не удалось.

Для <math>k \ge 3</math> k-конкурентные онлайновые k-серверные алгоритмы известны только для некоторых ограниченных метрических пространств, включая деревья [7], метрические пространства с числом точек до k + 2, а также манхэттенскую плоскость для k = 3 (см. [2, 6, 12]). Поскольку анализ алгоритма Algorithm для общего случая представляется сложным, любопытно было бы доказать его k-конкурентоспособность для некоторых отдельных случаев – например, на плоскости (с любой разумной метрикой) для <math>k \ge 4</math> серверов.

Мало что известно о коэффициенте конкурентоспособности k-серверной задачи для рандомизированного случая. Фактически неизвестно, даже можно ли получить коэффициент лучше 2 для k = 2.