4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 37: | Строка 37: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Теорема 1 подходит исключительно близко к доказательству k-серверной гипотезы, описанной ранее. Была даже высказано предположение, что сам алгоритм WFA является k- | Теорема 1 подходит исключительно близко к доказательству k-серверной гипотезы, описанной ранее. Была даже высказано предположение, что сам алгоритм WFA является k-конкурентным для k серверов, однако доказать его пока не удалось. | ||
Для <math>k \ge 3</math> k-конкурентные онлайновые k-серверные алгоритмы известны только для некоторых ограниченных метрических пространств, включая деревья [7], метрические пространства с числом точек до k + 2, а также манхэттенскую плоскость для k = 3 (см. [2, 6, 12]). Поскольку анализ алгоритма | Для <math>k \ge 3</math> k-конкурентные онлайновые k-серверные алгоритмы известны только для некоторых ограниченных метрических пространств, включая деревья [7], метрические пространства с числом точек до k + 2, а также манхэттенскую плоскость для k = 3 (см. [2, 6, 12]). Поскольку анализ алгоритма WFA для общего случая представляется сложным, любопытно было бы доказать его k-конкурентоспособность для некоторых отдельных случаев – например, на плоскости (с любой разумной метрикой) для <math>k \ge 4</math> серверов. | ||
Мало что известно о коэффициенте конкурентоспособности k-серверной задачи для рандомизированного случая. Фактически неизвестно, | Мало что известно о коэффициенте конкурентоспособности k-серверной задачи для рандомизированного случая. Фактически неизвестно даже, можно ли получить коэффициент лучше 2 для k = 2. | ||
== См. также == | == См. также == |
правок