4551
правка
Обобщенная двухсерверная задача: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обобщенная двухсерверная задача (посмотреть исходный код)
Версия от 12:03, 18 декабря 2017
, 18 декабря 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
== Основные результаты == | == Основные результаты == | ||
Основным результатом работы [ ] является достаточное условие наличия константно-конкурентного алгоритма для метрической системы сервисов. Кроме того, авторы продемонстрировали, что это условие выполняется и для обобщенной двухсерверной задачи. | Основным результатом работы [11] является достаточное условие наличия константно-конкурентного алгоритма для метрической системы сервисов. Кроме того, авторы продемонстрировали, что это условие выполняется и для обобщенной двухсерверной задачи. | ||
Для фиксированной метрической системы сервисов S с метрическим пространством M обозначим за A(C, | Для фиксированной метрической системы сервисов 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>, если он посещает все запросы по порядку. Следовательно, допустимым путем является такой путь, который обслуживает все запросы и начинается с исходной конфигурации. | ||