Системы метрических задач: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
Доказательство лучших известных на данный момент границ для n-точечной метрики общего вида производится в два этапа. Вначале заданная метрика аппроксимируется ''ультраметрикой'', а затем доказывается величина коэффициента конкурентоспособности общей задачи MTS | Доказательство лучших известных на данный момент границ для n-точечной метрики общего вида производится в два этапа. Вначале заданная метрика аппроксимируется ''ультраметрикой'', а затем доказывается величина коэффициента конкурентоспособности общей задачи MTS на ультраметрике. | ||
| Строка 54: | Строка 54: | ||
Фиат и Мендель [9] предложили O(log n log log n)-конкурентный алгоритм для n-точечных ультраметрик, улучшающий (и использующий) результат Бартала, Блюма, Берча и Томкинса [1], которые представили первый полилогарифмический (или даже сублинейный) конкурентный рандомизированный алгоритм решения общей задачи MTS | Фиат и Мендель [9] предложили O(log n log log n)-конкурентный алгоритм для n-точечных ультраметрик, улучшающий (и использующий) результат Бартала, Блюма, Берча и Томкинса [1], которые представили первый полилогарифмический (или даже сублинейный) конкурентный рандомизированный алгоритм решения общей задачи MTS на метрическом пространстве общего вида. | ||