Аноним

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

Материал из WEGA
м
Строка 34: Строка 34:




Теорема 1. Пусть S – метрическая система сервисов с метрическим пространством M. Предположим, что существует алгоритм A и константы a > 1; P > 0 и m > 2, такие, что для любой точки C 2 M последовательность a и попарно независимые пути T1, T2, ... , Tm, обслуживающие
Теорема 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>, выполняется соотношение
 
A(C, a) < aOPT(C, a) +
A(C, a) < aOPT(C, a) +
Тогда существует алгоритм B, являющийся константно-конкурентным для S.
Тогда существует алгоритм B, являющийся константно-конкурентным для S.


4551

правка