Обобщенная двухсерверная задача: различия между версиями

Основным результатом работы [11] является достаточное условие наличия константно-конкурентного алгоритма для метрической системы сервисов. Кроме того, авторы продемонстрировали, что это условие выполняется и для обобщенной двухсерверной задачи.

Для фиксированной метрической системы сервисов S с метрическим пространством <math>\mathbb{M} \;</math> обозначим за <math>A(C, \sigma) \;</math> стоимость работы алгоритма A на входной последовательности <math>\sigma \;</math>, начинающего работу с конфигурации C. Пусть <math>OPT(C, \sigma) \;</math> – стоимость соответствующего оптимального решения. Мы говорим, что путь T в <math>\mathbb{M} \;</math> ''обслуживает'' последовательность <math>\sigma \;</math>, если он посещает все запросы по порядку. Следовательно, допустимым путем является такой путь, который обслуживает все запросы и начинается с исходной конфигурации.

'''Теорема 1. Пусть S – метрическая система сервисов с метрическим пространством <math>\mathbb{M} \;</math>. Предположим, что существует алгоритм A и константы <math>\alpha \ge 1, \beta \ge 0, m \ge 2 \;</math>, такие, что для любой точки <math>C \in \mathbb{M} \;</math>, последовательности <math>\sigma \;</math> и попарно независимых путей <math>T_1, T_2, ... , T_m \;</math>, обслуживающих <math>\sigma \;</math>, выполняется соотношение'''

Множество метрических систем сервисов можно объединить, получив так называемую ''систему сумм'' [9]. Запрос к системе сумм включает по одному запросу к каждой системе, и для его обслуживания необходимо обслужить по меньшей мере один из отдельных запросов. Обобщенная двухсерверная задача может рассматриваться как одна из самых простых систем сумм, поскольку две отдельных задачи являются совершенно тривиальными: имеется один сервер, и каждый запрос состоит из одного пункта.