4551
правка
Аппроксимация метрических пространств древесными метриками: различия между версиями
Материал из WEGA
Аппроксимация метрических пространств древесными метриками (посмотреть исходный код)
Версия от 11:49, 31 октября 2016
, 31 октября 2016→Нотация
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Встраивание метрик общего вида в древесные метрики == Пост…») |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
Хотя в определении вероятностной аппроксимации используется распределение D над древесными метриками, нам бы хотелось найти процедуру, которая строила бы метрику случайного дерева, распределенную согласно D, т.е. такой алгоритм, который создавал бы метрику случайного дерева, вероятностно аппроксимирующую заданную метрику. Формальное определение задачи выглядит следующим образом. | Хотя в определении вероятностной аппроксимации используется распределение D над древесными метриками, нам бы хотелось найти процедуру, которая строила бы метрику случайного дерева, распределенную согласно D, т.е. такой алгоритм, который создавал бы метрику случайного дерева, вероятностно аппроксимирующую заданную метрику. Формальное определение задачи выглядит следующим образом. | ||
Задача (дерево аппроксимации) | |||
Дано: метрика (V, d) | |||
Требуется: построить древесную метрику (V, dT) выбранную из распределения T> над древесными метриками, которая a-вероятностно аппроксимирует ... | |||
Впоследствии Бартал определил класс древесных метрик, названных вполне разделенными иерархически деревьями (hierarchically well-separated trees, HST), следующим образом. Вполне разделенное k-иерархическое дерево (k-HST) представляет собой корневое взвешенное дерево, обладающее следующими двумя свойствами: веса ребер, ведущих от любой вершины к ее потомкам, равны; веса ребер на любом пути от вершины к листу уменьшаются не менее чем в k раз. Эти свойства важны для многих алгоритмов аппроксимации. | |||
Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой O(log n) – это лучший результат по сравнению с exp(O(log nloglog n)) в [ ]. Позднее Бартал [ ], применяя тот же подход, что и Сеймур при анализе задачи о множестве обратных дуг [ ], улучшил значение невязки до O(log n log log n). Используя процедуру округления Калинеску, Карлоффа и Рабани [ ], Факчаренфол, Рао и Талвар [ ] разработали алгоритм, ожидаемо вычисляющий дерево с невязкой O(log n). Эта граница привязана к константному коэффициенту. | |||
== Основные результаты == | |||
