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

Стандартный алгоритм, который доказуемо эффективно справляется с несколькими элементарными задачами маршрутизации – это так называемый ''алгоритм рабочей функции'' [2, 6, 8]. После каждого запроса алгоритм перемещается в конфигурацию с низкой стоимостью, находящуюся не слишком далеко от текущей конфигурации. Точнее говоря, если после обслуживания последовательности <math>\sigma \;</math> система имеет конфигурацию C, а <math>r \subseteq \mathbb{M} \;</math> – следующий запрос, то алгоритм рабочей функции с параметром <math>\lambda \ge 1 \;</math> переходит к конфигурации <math>C' \in r \;</math>, которая минимизирует соотношение <math>\lambda W_{\sigma, r} (C') + d(C, C') \;</math>, где d(C, C') – расстояние между конфигурациями C и C', а <math>W_{\sigma, r} (C') \;</math> – стоимость оптимального решения, обслуживающего все запросы (по порядку) в <math>\sigma \;</math> плюс запрос r с тем ограничением, что оно завершает работу в конфигурации C'.