Алгоритм DC-дерева для k серверов на деревьях: различия между версиями

В рамках ''k-серверной задачи'' мы хотим спланировать движение <math>k</math> серверов в метрическом пространстве <math>M</math> в ответ на последовательность <math>\varrho = r_{1}, r_{2},...,r_{n}</math>  

запросов, где <math>r_{i}\in M</math>  

для каждого <math>i</math>.  

Вначале все серверы расположены в одной и той же точке <math>r_{0}\in M</math>. После выдачи каждого запроса <math>r_{i}</math> один из <math>k</math> серверов должен переместиться в <math>r_{i}</math>. ''План'' определяет, какой сервер перемещается по каждому запросу. ''Стоимость'' плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью.

В ''онлайн-версии'' k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за <math>cost_{A}(\varrho)</math> стоимость плана, производимого алгоритмом A на последовательности запросов <math>\varrho</math>

, а за <math>opt(\varrho)</math> -

стоимость оптимального плана. Назовем алгоритм A ''R-конкурентным'', если <math>cost_{A}(\varrho) < R \cdot opt(\varrho) + B</math>, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется ''коэффициентом конкурентоспособности'' A. Разумеется, чем меньше R, тем лучше.

k-серверная задача была предложена Манассом, Макгиохом и Слейтором [7, 8], доказавшими, что не существует R-конкурентного онлайн-алгоритма для R < k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть ''k-серверной гипотезой'', которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [5, 6] доказали, что так называемый ''алгоритм рабочей функции'' имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница.