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

В ''онлайн-версии'' k-серверной задачи решение о том, к какому серверу следует переместиться для каждого запроса <math>r_i</math>, должно приниматься до выдачи следующего запроса <math>r_{i + 1}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Обозначим за <math>cost_{\mathcal{A}}(\rho)</math> стоимость плана, производимого онлайн-алгоритмом A для k-серверной задачи на последовательности запросов *, а за opt(*) – стоимость оптимального плана на этой последовательности. Назовем алгоритм A R-конкурентным, если costA(*) < R – opt(*) + B, где B – константа, которая может зависеть от M и X0. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше.

k-серверная задача была предложена Манассом, Макгиохом и Слейтором [13,14], доказавшими, что ни один (детерминированный) онлайн-алгоритм не может достичь коэффициента конкурентоспособности меньше k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть k-серверной гипотезой, которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [10, 11] (см. также [3, 8, 9]) доказали, что так называемый алгоритм рабочей функции, представленный далее, имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница.