Системы метрических задач: различия между версиями

Если X конечно, а последовательность задач <math>\tau \in T^* \;</math> задана заранее, динамический алгоритм может вычислить оптимальное решение, используя память размером <math>O(|X|) \;</math> и время <math>О(| \tau | \cdot |X|) \;</math>. Однако задача MTS интереснее всего в онлайновом режиме, в котором система должна реагировать на задачу <math>\tau_i \;</math> переходом в состояние <math>a_i \in X \;</math>, не зная будущих задач из <math>\tau \;</math>. Более формально:

'''Определение 2 (онлайн-алгоритмы для MTS)'''. Детерминированный алгоритм решения задачи <math>MTS((X, d_X), T, a_0) \;</math> представляет собой отображение <math>S: T^* \to X^* \;</math>, такое, что для любого <math>\tau \in T \;</math> имеет место <math>|S(\tau)| = |\tau| \;</math> . Детерминированный алгоритм <math>S: T^* \to X^* \;</math> называется ''онлайновым'', если для любых <math>\tau, \sigma \in T^* \;</math> существует <math>a \in X^*, |a| = | \sigma | \;</math>, такое, что <math>S(\tau \circ \sigma) = S(\tau) \circ a \;</math>. Рандомизированный онлайн-алгоритм представляет собой вероятностное распределение над детерминированными онлайн-алгоритмами.

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

Доказательство лучших известных на данный момент границ для n-точечной метрики общего вида производится в два этапа. Вначале заданная метрика аппроксимируется ''ультраметрикой'', а затем доказывается граница коэффициента конкурентоспособности общей задачи MTS на ультраметрике.

Фиат и Мендель [9] предложили O(log n log log n)-конкурентный алгоритм для n-точечных ультраметрик, улучшающий (и использующий) результат Бартала, Блюма, Берча и Томкинса [1], которые представили первый полилогарифмически- (или даже сублинейно)-конкурентный рандомизированный алгоритм решения общей задачи MTS на метрическом пространстве общего вида.

Компонент аппроксимации метрики, упоминающийся в доказательстве теоремы 4, называется ''подмножествами Рамсея''. Первыми в этом контексте его использовали Карлофф, Рабани и Равид, впоследствии результат улучшили Блюм, Карлофф, Рабани и Сакс, а также Бартал, Боллобас и Мендель [2]. Строгий результат для подмножеств Рамсея доказали Бартал, Линиал, Мендель и Наор. Более простое (и строгое) доказательство можно найти в работе [12].

Нижняя граница <math>\Omega (log \; n /log \; log \; n)</math> коэффициента конкурентоспособности любого рандомизированного алгоритма решения общей задачи MTS на n-точечной ультраметрике была доказана в [2], улучшив тем самым предыдущие результаты Карлоффа, Рабани и Равида, а также Блюма, Карлоффа, Рабани и Сакса.

'''Теорема 5 [6]. Задача определения коэффициента конкурентоспособности для данного экземпляра задачи <math>MTS ((X, d_X), a_0 \in X, T) \;</math> является [[PSPACE-hard problem|PSPACE-трудной]], даже если метрика <math>d_X \;</math> является униформной. С другой стороны, если метрика <math>d_X \;</math> является униформной, существует детерминированный онлайн-алгоритм с полиномиальным временем выполнения для решения задачи <math>MTS((X, d_X), a_0 \in X, T) \;</math>, коэффициент конкурентоспособности которого в O(log |X|) раз превышает детерминированный коэффициент конкурентоспособности алгоритма для <math>MTS((X, d_X), a_0, T) \;</math>. Предполагается, что экземпляр <math>((X, d_X), a_0, T) \;</math> задан явным образом.'''

Системы метрических задач были введены в качестве абстракции для онлайн-вычислений, они обобщают многие конкретные задачи онлайн-вычислений, такие как подкачка, взвешенное кэширование, k-серверная задача и обновление списков. Исторически они служили индикаторами для общей теории конкурентных онлайн-вычислений.

Основным техническим вкладом модели MTS является разработка алгоритма рабочей функции, используемого для доказательства верхней границы в теореме 1. Кутсупиас и Пападимитриу впоследствии проанализировали этот алгоритм в контексте k-серверной задачи и показали, что он является (2k - 1)-конкурентным. Кроме того, хотя модель MTS служит обобщением k-серверной задачи, общая задача MTS на n-точечной метрике по существу эквивалентна (n - 1)-серверной задаче на той же метрике [2]. Следовательно, из нижних границ коэффициента конкурентоспособности общей задачи MTS можно получить нижние границы для k-серверной задачи, а алгоритмы решения общей задачи MTS могут стать первым шагом к разработке алгоритма для решения k-серверной задачи, как и в случае с алгоритмом рабочей функции.