4551
правка
Системы метрических задач: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1 [5]. Детерминированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного метрического пространства равен 2n - 1. | |||
В отличие от детерминированного случая для рандомизированных алгоритмов решения общей задачи MTS пока не сложилось полного понимания, и для общего случая неизвестны точные границы, подобные приведенным в теореме 1. | |||
Теорема 2 [5,10]. Рандомизированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного униформного пространства (в котором все расстояния равны) составляет не менее Hn = Pni=1 *~l> и не более (1 + o(1))Hn. | |||
Доказательство лучших известных на данный момент границ для n-точечной метрики общего вида производится в два этапа. Вначале заданная метрика аппроксимируется ультраметрикой, а затем доказывается величина коэффициента конкурентоспособности общей задачи MTS над ультраметрикой. | |||
Теорема 3 [8, 9]. Для любого n-точечного метрического пространства (X, dX) существует O(log и log log n)-конкурентный рандомизированный алгоритм решения общей задачи MTS на (X, dX). | |||
Компонент аппроксимации метрики, упоминающийся в доказательстве теоремы 3, называется вероятностным вложением. Оптимальное O(log n)-вероятностное вложение предложили Факчеренфол, Рао и Талвар [8], улучшившие результат Алона, Карпа, Пелега и Уэста, а также Бартала, который ввел это понятие. Другой тип аппроксимации метрики с лучшими границами для метрик с низкой пропорциональностью представлен в [3]. | |||
Фиат и Мендель [ ] предложили O(log n log log n)-конкурентный алгоритм для n-точечных ультраметрик, улучшающий (и использующий) результат Бартала, Блюма, Берча и Томкинса [ ], которые представили первый полилогарифмический (или даже сублинейный) конкурентный рандомизированный алгоритм решения общей задачи MTS над метрическим пространством общего вида. | |||
Теорема 4 [2, 12]. Для любого n-точечного метрического пространства (X, dX) рандомизированный коэффициент конкурентоспособности для общей задачи MTS на (X, dX) составляет не менее Q (log n/log log n). | |||
Компонент аппроксимации метрики, упоминающийся в доказательстве теоремы 4, называется подмножествами Рамсея. Первыми в этом контексте его использовали Карлофф, Рабани и Равид, впоследствии результат улучшили Блюм, Карлофф, Рабани и Сакс, а также Бартал, Боллобас и Мендель [ ]. Строгий результат для подмножеств Рамсея доказали Бартал, Линиал, Мендель и Наор. Более простое (и строгое) доказательство можно найти в работе [12]. | |||
Нижняя граница £?(log n/log log n) коэффициента конкурентоспособности любого рандомизированного алгоритма решения общей задачи MTS на n-точечной ультраметрике доказана в [ ], улучшив тем самым предыдущие результаты Карлоффа, Рабани и Равида, а также Блюма, Карлоффа, Рабани и Сакса. | |||
Следующая теорема, в отличие от остальных, не рассматривает общую задачу MTS. | |||
Теорема 5 [6]. Задача определения коэффициента конкурентоспособности для данного экземпляра задачи MTS ((X, dX), a0 2 X, T) является PSPACE-полной, даже если метрика dX является униформной. С другой стороны, если метрика dX является униформной, существует детерминированный онлайн-алгоритм с полиномиальным временем выполнения для решения задачи MTS((X, dX), a0 2 X, T), коэффициент конкурентоспособности которого в O(log jXj) раз превышает детерминированный коэффициент конкурентоспособности алгоритма для MTS((X, dX), a0, T). Предполагается, что экземпляр ((X, dX), a0, T) задан явным образом. | |||
== Применение == | |||
Системы метрических задач были введены в качестве абстракции для онлайн-вычислений, они обобщают многие конкретные задачи онлайн-вычислений, такие как подкачка, взвешенное кэширование, k-серверная задача и обновление списков. Исторически она служила индикатором для общей теории конкурентных онлайн-вычислений. | |||
Основным техническим вкладом модели MTS является разработка алгоритма рабочей функции, используемого для доказательства верхней границы в теореме 1. Кутсупиас и Пападимитриу впоследствии проанализировали этот алгоритм в контексте k-серверной задачи и показали, что он является 2k-1-конкурентным. Кроме того, хотя модель MTS служит обобщением k-серверной задачи, общая задача MTS на n-точечной метрике по существу эквивалентна (n - 1)-серверной задаче на той же метрике [2]. Следовательно, из нижних границ коэффициента конкурентоспособности общей задачи MTS можно получить нижние границы для k-серверной задачи, а алгоритмы решения общей задачи MTS могут стать первым шагом к разработке алгоритма для решения k-серверной задачи, как и в случае с алгоритмом рабочей функции. | |||
Аппроксимации метрики, использовавшиеся в теоремах 3 и 4, нашли немало других алгоритмических применений. | |||
== Открытые вопросы == | |||