4511
правок
Системы метрических задач: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1 [5]. Детерминированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного метрического пространства равен 2n - 1. | '''Теорема 1 [5]. Детерминированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного метрического пространства равен 2n - 1.''' | ||
| Строка 42: | Строка 42: | ||
Теорема 2 [5,10]. Рандомизированный коэффициент конкурентоспособности общей задачи MTS для любого n-точечного униформного пространства (в котором все расстояния равны) составляет не менее | '''Теорема 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 над ультраметрикой. | Доказательство лучших известных на данный момент границ для n-точечной метрики общего вида производится в два этапа. Вначале заданная метрика аппроксимируется ''ультраметрикой'', а затем доказывается величина коэффициента конкурентоспособности общей задачи MTS над ультраметрикой. | ||
Теорема 3 [8, 9]. Для любого n-точечного метрического пространства (X, | '''Теорема 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-точечного метрического пространства (X, | |||
'''Теорема 4 [2, 12]. Для любого n-точечного метрического пространства <math>(X, d_X) \;</math> рандомизированный коэффициент конкурентоспособности для общей задачи MTS на <math>(X, d_X) \;</math> составляет не менее <math>\Omega (log \; n /log \; log \; n)</math>.''' | |||