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

Если 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 \sigma \;</math>. Рандомизированный онлайн-алгоритм представляет собой вероятностное распределение над детерминированными онлайн-алгоритмами.

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

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

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

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

По-прежнему сохраняется очевидный разрыв между верхней и нижней границами рандомизированного коэффициента конкурентоспособности общей задачи MTS над конечной метрикой общего вида. Известно, что,  в отличие от детерминированного случая, рандомизированный коэффициент конкурентоспособности не является константным над всеми метрическими пространствами того же размера. Однако в случаях, когда известны точные границы, коэффициент конкурентоспособности  равен <math>\Theta(log \; n)</math>. Из этого можно сделать очевидный вывод, что для любой n-точечной метрики рандомизированный коэффициент конкурентоспособности равен <math>\Theta(log \; n)</math>. Вероятно, самыми простыми классами метрических пространств, для которых неизвестна верхняя граница рандомизированного коэффициента конкурентоспособности лучше <math>O(log^2 n) \;</math>, являются пути и циклы.

Хотелось бы усилить формулировку теоремы 5 и получить детерминированный онлайн-алгоритм с полиномиальным временем выполнения, коэффициент конкурентоспособности которого для любого экземпляра задачи MTS на ''любом'' n-точечном метрическом пространстве не более чем в poly-log(n) превышает детерминированный коэффициент конкурентоспособности для этого экземпляра.