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

В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов в метрическом пространстве <math>\mathbb{M}</math> в ответ на последовательность <math>\rho = r_1, r_2, ..., r_n</math> ''запросов'', где <math>r_i \in M</math> для каждого i. Вначале все серверы занимают одну и ту же конфигурацию <math>X_0 \subseteq \mathbb{M}</math>. После выдачи каждого запроса <math>r_i</math> один из k серверов должен переместиться в <math>r_i</math>. План S определяет, какой сервер перемещается по каждому запросу. Задача заключается в создании ''плана'' минимальной стоимости, где стоимость плана равна сумме расстояний, пройденных серверами. Ниже приводится пример плана для 2 серверов на последовательности запросов.

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