4551
правка
Аппроксимация метрических пространств древесными метриками: различия между версиями
Перейти к навигации
Перейти к поиску
Аппроксимация метрических пространств древесными метриками (посмотреть исходный код)
Версия от 17:55, 31 октября 2016
, 31 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
Граница в теореме 1 является точной, поскольку Алон и др. [1] доказали границу невязки J2(logn) в случае, когда (V, d) порождается графом-решеткой. Также стоит отметить, что существует убеждение, что даже встраивание линейной метрики в 2-HST-дерево приводит к невязке £?(log n). | Граница в теореме 1 является точной, поскольку Алон и др. [1] доказали границу невязки J2(logn) в случае, когда (V, d) порождается графом-решеткой. Также стоит отметить, что существует убеждение, что даже встраивание линейной метрики в 2-HST-дерево приводит к невязке £?(log n). | ||
Если дерево должно быть k-HST-деревом, можно применить результат Бартала, Чарикара и Раза [ ], который заключается в том, что любое 2-HST-дерево может быть O(k/log k)-вероятностно аппроксимировано k-HST-деревом с получением ожидаемой невязки O(klogn/logk). | |||
Задача поиска распределения древесных метрик, вероятностно аппроксимирующее заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева T с малым средним взвешенным растяжением. Более конкретно, пусть даны веса ребер cuv; необходимо найти древесную метрику dT, такую, что для всех u, v 2 VdT (u, v) > d(u, v) и Pu,v 2 V cuvdT(u,v) < uJ2u, vev cuvd(u,v). | |||
Чарикар, Чекури, Гель, Гуха и Плоткин [6] показали, как найти распределение O(n log n) древесных метрик, a-вероятностно аппроксимирующее заданную метрику, при условии возможности решения двойственной задачи. Алгоритм теоремы 1 может быть дерандомизирован при помощи метода с использованием условного матожидания, что дает в результате требуемую древесную метрику a = O(log n). Еще один алгоритм, основанный на модификации техники наращивания областей, был представлен в [ ] и независимо от этого – в работе Бартала. | |||
Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение D над O(nlogn) древесных метрик, которая O(log n)-вероятностно аппроксимирует (V, d). | |||
Отметим, что дерево на выходе алгоритма содержит вершины Штейнера; однако Гупта Gupta [10] показал, как найти другую древесную метрику, не содержащую вершин Штейнера и при этом сохраняющую все расстояния с поправкой на константный коэффициент. | |||
== Применение == | |||