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

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

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

Нотация

Обозначим за T* множество конечных последовательностей элементов множества T. Для [math]\displaystyle{ x, y \in T^* \; }[/math] обозначим за [math]\displaystyle{ x \circ y }[/math] конкатенацию последовательностей x и y, а за |x| – длину последовательности x.

Определение 1 (система метрических задач). Зафиксируем метрическое пространство [math]\displaystyle{ (X, d_X) \; }[/math]. Пусть [math]\displaystyle{ \Gamma = \{ (r_x)_{x \in X}: \forall x \in X, r(x) \in [0, \infty] \} }[/math] – множество всех возможных задач. Обозначим за [math]\displaystyle{ T \subset \Gamma \; }[/math] подмножество задач, называемых допустимыми.

[math]\displaystyle{ MTS((X, d_X), T, a_0 \in X) \; }[/math]:

Дано: конечная последовательность задач [math]\displaystyle{ \tau = (\tau_1, ..., \tau_m) \in T^* \; }[/math].

Требуется: найти последовательность точек [math]\displaystyle{ a = (a_1, ..., a_m) \in X^*, |a| = |\tau| \; }[/math],

Цель: минимизировать [math]\displaystyle{ cost(\tau, a) = \sum_{i = 1}^m (d_X(a_{i - 1}, a_i) + \tau_i(a_i)) }[/math].

В случае [math]\displaystyle{ T = \Gamma \; }[/math] задача MTS называется общей.

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

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

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

Определение 3. Рандомизированный онлайн-алгоритм R для задачи [math]\displaystyle{ MTS((X, d_X), T, a_0) \; }[/math] называется c-конкурентным (по сравнению с рассеянными соперниками), если существует [math]\displaystyle{ b = b(X) \in \mathbb{R} \; }[/math], такое, что для любой последовательности задач [math]\displaystyle{ \tau \in T^* \; }[/math] и любой последовательности точек [math]\displaystyle{ a \in X^*, |a| = | \tau | \; }[/math] имеет место соотношение [math]\displaystyle{ \mathbb{E} [cost(\tau, R(\tau))] \le c \cdot cost(\tau, a) + b \; }[/math], где математическое ожидание берется над распределением R.

Коэффициентом конкурентоспособности онлайн-алгоритма R является инфимум над [math]\displaystyle{ c \ge 1 \; }[/math], для которого R является c-конкурентным. Детерминированным [соответственно, рандомизированным] коэффициентом конкурентоспособности задачи [math]\displaystyle{ MTS((X, d_X), T, a_0) \; }[/math] является инфимум над коэффициентами конкурентоспособности всех детерминированных [соответственно, рандомизированных] онлайн-алгоритмов для этой задачи. Отметим, что в силу наличия квантора существования при b асимптотический коэффициент конкурентоспособности (как рандомизированный, так и детерминированный) задачи [math]\displaystyle{ MTS((X, d_X), T, a_0) \; }[/math] независим от [math]\displaystyle{ a_0 \; }[/math] и, следовательно, может быть исключен из нотации.

Основные результаты

Теорема 1 [5]. Детерминированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного метрического пространства равен 2n - 1.

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

Теорема 2 [5,10]. Рандомизированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного униформного пространства (в котором все расстояния равны) составляет не менее [math]\displaystyle{ H_n = \sum_{i = 1}^{n - 1} i^{-1} }[/math] и не более [math]\displaystyle{ (1 + o(1))H_n \; }[/math].

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

Теорема 3 [8, 9]. Для любого n-точечного метрического пространства [math]\displaystyle{ (X, d_X) \; }[/math] существует [math]\displaystyle{ O(log^2 n \; log \; log \; n) }[/math]-конкурентный рандомизированный алгоритм решения общей задачи MTS на [math]\displaystyle{ (X, d_X) \; }[/math].

Компонент аппроксимации метрики, упоминающийся в доказательстве теоремы 3, называется вероятностным вложением. Оптимальное O(log n)-вероятностное вложение предложили Факчеренфол, Рао и Талвар [8], улучшившие результат Алона, Карпа, Пелега и Уэста, а также Бартала, который ввел это понятие. Другой тип аппроксимации метрики с лучшими границами для метрик с низкой пропорциональностью представлен в [3].

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

Теорема 4 [2, 12]. Для любого n-точечного метрического пространства [math]\displaystyle{ (X, d_X) \; }[/math] рандомизированный коэффициент конкурентоспособности для общей задачи MTS на [math]\displaystyle{ (X, d_X) \; }[/math] составляет не менее [math]\displaystyle{ \Omega (log \; n /log \; log \; n) }[/math].

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

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

Следующая теорема, в отличие от остальных, не рассматривает общую задачу MTS.

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

Применение

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

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

Аппроксимации метрики, использовавшиеся в теоремах 3 и 4, нашли немало других алгоритмических применений.