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

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

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