Системы метрических задач

Постановка задачи

Понятие системы метрических задач (Metrical task systems, MTS) было введено Бородиным, Линиалом и Саксом [5]. Она представляет собой задачу о минимизации стоимости, определенную на метрическом пространстве [math]\displaystyle{ (X, d_X) \; }[/math], и может быть неформально описана следующим образом. Дана система с множеством внутренних состояний X. Задача системы заключается в обслуживании заданной последовательности задач. Обслуживание каждой задачи имеет определенную стоимость, зависящую от самой задачи и от состояния системы. Система может поменять состояние перед обслуживанием задачи, так что общая стоимость обслуживания задачи будет равна сумме стоимости обслуживания задачи в новом состоянии и расстоянию между состояниями в метрическом пространстве, определенном на множестве состояний. Манасс, Макгиох и Слейтор [11] предложили расширенную модель, которая будет рассмотрена далее и в которой множество допустимых задач может быть ограничено.

Нотация

Обозначим за Г* множество конечных последовательностей элементов множества T. Для x, y 2 T* обозначим за x о y конкатенацию последовательностей x и y, а за |x| – длину последовательности x.

Определение 1 (система метрических задач). Зафиксируем метрическое пространство (X, dX). Пусть Г = f(rx)x2X 8x2X; r(x) 2 [0;1]g – множество всех возможных задач. Обозначим за T С Г подмножество задач, называемых допустимыми.

MTS((X, dX), T,a0 2 X): Дано: Конечная последовательность задач x = (xi1 , m) 2 Г*. Требуется: Найти последовательность точек a = (a1.. am) 2 X*, И = 14 Цель: минимизировать cost(r, a) = В случае T = Г задача MTS называется общей.

Если X конечно, а последовательность задач x 2 Г* задана заранее, динамический алгоритм может вычислить оптимальное решение, используя память размером O(|X|) и время О(|т| • |X|). Задача MTS интереснее всего в онлайновом режиме, в котором система должна реагировать на задачу x\ переходом в состояние ai 2 X, не зная будущих задач из x. Более формально:

Определение 2 (онлайн-алгоритмы для MTS). Детерминированный алгоритм решения задачи MTS((X, dX), T, a0) представляет собой отображение S: Г* ! X*, такое, что для любого x 2 T имеет место |S(T)| = \x . Детерминированный алгоритм S: Г* ! X* называется онлайновым, если для любых x, a 2 T*, существует a 2 X*, jaj = \a\, такое, что S(x о a) = S(x) о a. Рандомизированный онлайн-алгоритм представляет собой вероятностное распределение над детерминированными онлайн-алгоритмами.

Онлайн-алгоритмы для MTS оцениваются с помощью (асимптотического) конкурентного анализа, который, грубо говоря, вычисляет наихудшее отношение стоимости алгоритма к оптимальной стоимости по всем возможным последовательностям задач.

Определение 3. Рандомизированный онлайн-алгоритм R для задачи MTS((X, dX), a0) называется c-конкурентным (по сравнению с рассеянными соперниками), если существует b = b(X) 2 R, такое, что для любой последовательности задач x 2 T* и любой последовательности точек a 2 X*, N = 14 имеет место соотношение E[cost(T,i?(r))] < c-cost(r, a) + b, где математическое ожидание берется над распределением R.

Коэффициентом конкурентоспособности онлайн-алгоритма R является инфимум над c > 1, для которого R является c-конкурентным. Детерминированным [соответственно, рандомизированным] коэффициентом конкурентоспособности задачи MTS((X, dX), T, a0) является инфимум над коэффициентами конкурентоспособности всех детерминированных [соответственно, рандомизированных] онлайн-алгоритмов для этой задачи. Отметим, что в силу наличия квантора существования при b асимптотический коэффициент конкурентоспособности (как рандомизированный, так и детерминированный) задачи MTS((X, dX), T, a0) независим от a0 и, следовательно, может быть исключен из нотации.