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