4446
правок
Системы метрических задач: различия между версиями
Материал из WEGA
м
→Открытые вопросы
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Понятие системы метрических задач (Metrical task systems, MTS) было введено Бо…») |
Irina (обсуждение | вклад) |
||
| (не показано 16 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Понятие системы метрических задач (Metrical task systems, MTS) было введено Бородиным, Линиалом и Саксом [5]. Она представляет собой задачу о минимизации стоимости, определенную на метрическом пространстве (X, | Понятие системы метрических задач (Metrical task systems, MTS) было введено Бородиным, Линиалом и Саксом [5]. Она представляет собой задачу о минимизации стоимости, определенную на метрическом пространстве <math>(X, d_X) \;</math>, и может быть неформально описана следующим образом. Дана ''система'' с множеством внутренних состояний X. Задача системы заключается в обслуживании заданной последовательности задач. Обслуживание каждой задачи имеет определенную стоимость, зависящую от самой задачи и от состояния системы. Система может поменять состояние перед обслуживанием задачи, так что общая стоимость обслуживания задачи будет равна сумме стоимости обслуживания задачи в новом состоянии и расстоянию между состояниями в метрическом пространстве, определенном на множестве состояний. Манасс, Макгиох и Слейтор [11] предложили расширенную модель, которая будет рассмотрена далее и в которой множество допустимых задач может быть ограничено. | ||
== Нотация == | == Нотация == | ||
Обозначим за | Обозначим за T* множество конечных последовательностей элементов множества T. Для <math>x, y \in T^* \;</math> обозначим за <math>x \circ y</math> конкатенацию последовательностей x и y, а за |x| – длину последовательности x. | ||
Определение 1 (система метрических задач). Зафиксируем метрическое пространство (X, | '''Определение 1 (система метрических задач)'''. Зафиксируем метрическое пространство <math>(X, d_X) \;</math>. Пусть <math>\Gamma = \{ (r_x)_{x \in X}: \forall x \in X, r(x) \in [0, \infty] \}</math> – множество всех возможных задач. Обозначим за <math>T \subset \Gamma \;</math> подмножество задач, называемых ''допустимыми''. | ||
<math>MTS((X, d_X), T, a_0 \in X) \;</math>: | |||
''Дано'': конечная последовательность задач <math>\tau = (\tau_1, ..., \tau_m) \in T^* \;</math>. | |||
Дано: | |||
''Требуется'': найти последовательность точек <math>a = (a_1, ..., a_m) \in X^*, |a| = |\tau| \;</math>, | |||
''Цель'': минимизировать <math>cost(\tau, a) = \sum_{i = 1}^m (d_X(a_{i - 1}, a_i) + \tau_i(a_i))</math>. | |||
В случае <math>T = \Gamma \;</math> задача MTS называется ''общей''. | |||
Если 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 оцениваются с помощью ''(асимптотического) конкурентного анализа'', который, грубо говоря, вычисляет наихудшее отношение стоимости алгоритма к оптимальной стоимости по всем возможным последовательностям задач. | |||
Коэффициентом конкурентоспособности онлайн-алгоритма R является инфимум над c > | |||
'''Определение 3'''. Рандомизированный онлайн-алгоритм R для задачи <math>MTS((X, d_X), T, a_0) \;</math> называется c-конкурентным (по сравнению с рассеянными соперниками), если существует <math>b = b(X) \in \mathbb{R} \;</math>, такое, что для любой последовательности задач <math>\tau \in T^* \;</math> и любой последовательности точек <math>a \in X^*, |a| = | \tau | \;</math> | |||
имеет место соотношение <math>\mathbb{E} [cost(\tau, R(\tau))] \le c \cdot cost(\tau, a) + b \;</math>, где математическое ожидание берется над распределением R. | |||
Коэффициентом конкурентоспособности онлайн-алгоритма R является инфимум над <math>c \ge 1 \;</math>, для которого R является c-конкурентным. Детерминированным [соответственно, рандомизированным] коэффициентом конкурентоспособности задачи <math>MTS((X, d_X), T, a_0) \;</math> является инфимум над коэффициентами конкурентоспособности всех детерминированных [соответственно, рандомизированных] онлайн-алгоритмов для этой задачи. Отметим, что в силу наличия квантора существования при ''b'' асимптотический коэффициент конкурентоспособности (как рандомизированный, так и детерминированный) задачи <math>MTS((X, d_X), T, a_0) \;</math> независим от <math>a_0 \;</math> и, следовательно, может быть исключен из нотации. | |||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 1 [5]. Детерминированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного метрического пространства равен 2n - 1.''' | |||
В отличие от детерминированного случая, для рандомизированных алгоритмов решения общей задачи MTS пока не сложилось полного понимания, и для общего случая неизвестны точные границы, подобные приведенным в теореме 1. | |||
'''Теорема 2 [5,10]. Рандомизированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного униформного пространства (в котором все расстояния равны) составляет не менее <math>H_n = \sum_{i = 1}^{n - 1} i^{-1}</math> и не более <math>(1 + o(1))H_n \;</math>.''' | |||
Доказательство лучших известных на данный момент границ для n-точечной метрики общего вида производится в два этапа. Вначале заданная метрика аппроксимируется ''ультраметрикой'', а затем доказывается граница коэффициента конкурентоспособности общей задачи MTS на ультраметрике. | |||
'''Теорема 3 [8, 9]. Для любого n-точечного метрического пространства <math>(X, d_X) \;</math> существует <math>O(log^2 n \; log \; log \; n)</math>-конкурентный рандомизированный алгоритм решения общей задачи MTS на <math>(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>(X, d_X) \;</math> рандомизированный коэффициент конкурентоспособности для общей задачи MTS на <math>(X, d_X) \;</math> составляет не менее <math>\Omega (log \; n /log \; log \; n)</math>.''' | |||
Компонент аппроксимации метрики, упоминающийся в доказательстве теоремы 4, называется ''подмножествами Рамсея''. Первыми в этом контексте его использовали Карлофф, Рабани и Равид, впоследствии результат улучшили Блюм, Карлофф, Рабани и Сакс, а также Бартал, Боллобас и Мендель [2]. Строгий результат для подмножеств Рамсея доказали Бартал, Линиал, Мендель и Наор. Более простое (и строгое) доказательство можно найти в работе [12]. | |||
Нижняя граница <math>\Omega (log \; n /log \; log \; n)</math> коэффициента конкурентоспособности любого рандомизированного алгоритма решения общей задачи MTS на n-точечной ультраметрике была доказана в [2], улучшив тем самым предыдущие результаты Карлоффа, Рабани и Равида, а также Блюма, Карлоффа, Рабани и Сакса. | |||
Следующая теорема, в отличие от остальных, не рассматривает общую задачу MTS. | |||
'''Теорема 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-серверной задачи, как и в случае с алгоритмом рабочей функции. | |||
Аппроксимации метрики, использовавшиеся в теоремах 3 и 4, нашли немало других алгоритмических применений. | |||
== Открытые вопросы == | |||
По-прежнему сохраняется очевидный разрыв между верхней и нижней границами рандомизированного коэффициента конкурентоспособности общей задачи MTS над конечными метриками общего вида. Известно, что, в отличие от детерминированного случая, рандомизированный коэффициент конкурентоспособности ''не является константным'' над всеми метрическими пространствами того же размера. Однако в случаях, когда известны точные границы, коэффициент конкурентоспособности равен <math>\Theta(log \; n)</math>. Из этого можно сделать очевидный вывод, что для любой n-точечной метрики рандомизированный коэффициент конкурентоспособности равен <math>\Theta(log \; n)</math>. Вероятно, самыми простыми классами метрических пространств, для которых неизвестна верхняя граница рандомизированного коэффициента конкурентоспособности лучше <math>O(log^2 n) \;</math>, являются пути и циклы. | |||
Кроме того, не хватает «средней теории» для задачи MTS. С одной стороны, общая задача MTS достаточно хорошо изучена. С другой же стороны, такие специализированные задачи MTS, как обновление списков, детерминированные k-серверные алгоритмы и детерминированное взвешенное кэширование, также хорошо изучены и имеют намного лучшие коэффициенты конкурентоспособности по сравнению с соответствующей общей задачей. На данный момент недостает «промежуточных» моделей MTS, которые могли бы объяснить низкие коэффициенты конкурентоспособности для некоторых конкретных онлайн-задач, упомянутых выше. | |||
Хотелось бы усилить формулировку теоремы 5 и получить детерминированный онлайн-алгоритм с полиномиальным временем выполнения, коэффициент конкурентоспособности которого для любого экземпляра задачи MTS на ''любом'' n-точечном метрическом пространстве не более чем в poly-log(n) раз превышает детерминированный коэффициент конкурентоспособности для этого экземпляра. | |||
== См. также == | |||
* [[Алгоритм DC-дерева для k серверов на деревьях]] | |||
* [[Аппроксимация метрических пространств древесными метриками]] | |||
* [[Онлайн-алгоритм обновления списков]] | |||
* [[Онлайн-алгоритм подкачки и кэширования]] | |||
* [[Подкачка страниц]] | |||
* [[Задача об аренде лыж]] | |||
* [[Алгоритм рабочей функции для k серверов]] | |||
== Литература == | |||
1. Bartal, Y., Blum, A., Burch, C., Tomkins, A.: A polylog()-competitive algorithm for metrical task systems. In: Proceedings of the 29th annual ACM Symposium on the Theory of Computing, pp. 711-719. ACM, New York (1997) | |||
2. Bartal, Y., Bollobas, B., Mendel, M.: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst.Sci. 72,890-921 (2006) | |||
3. Bartal, Y., Mendel, M.: Multiembedding of metric spaces. SIAM J. Comput. 34, 248-259 (2004) | |||
4. Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, Cambridge, UK (1998) | |||
5. Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM 39, 745-763 (1992) | |||
6. Burley, W.R., Irani, S.: On algorithm design for metrical task systems. Algorithmica 18,461^85 (1997) | |||
7. Chrobak, M., Larmore, L.L.: Metrical task systems, the server problem and the work function algorithm. In: Fiat, A., Woeginger, G J. (eds.) Online Algorithms. The State of the Art. LNCS, vol. 1442, ch.4, pp. 74-96. Springer, London (1998) | |||
8. Fakcharoenphol, J., Rao, S.,Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69,485-497(2004) | |||
9. Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. SIAM J. Comput. 32, 1403-1422 (2003) | |||
10. Irani, S., Seiden, S.S.: Randomized algorithms for metrical task systems. Theor. Comput. Sci. 194,163-182 (1998) | |||
11. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11,208-230 (1990) | |||
12. Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. 9(2), 253-275 (2007) | |||
