4551
правка
Обобщенная двухсерверная задача: различия между версиями
Материал из WEGA
Обобщенная двухсерверная задача (посмотреть исходный код)
Версия от 12:11, 18 декабря 2017
, 18 декабря 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
Теорема 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>, выполняется соотношение | '''Теорема 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, | '''(1) <math>A(C, \sigma) \le \alpha OPT(C, \sigma) + \beta \sum^m_{i = 1} | T_i |</math>.''' | ||
Тогда существует алгоритм B, являющийся константно-конкурентным для S. | '''Тогда существует алгоритм B, являющийся константно-конкурентным для S.''' | ||
