4551
правка
Аппроксимация метрических пространств древесными метриками: различия между версиями
Перейти к навигации
Перейти к поиску
Аппроксимация метрических пространств древесными метриками (посмотреть исходный код)
Версия от 11:37, 1 ноября 2016
, 1 ноября 2016→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
== Нотация == | == Нотация == | ||
Граф G = (V, E), ребрам которого присвоены неотрицательные веса, определяет метрическое пространство (V, | Граф G = (V, E), ребрам которого присвоены неотрицательные веса, определяет метрическое пространство <math>(V, d_G) \;</math>, где для каждой пары вершин <math>u, v \in V \;</math> за <math>d_G(u, v) \;</math> обозначается расстояние по кратчайшему пути между u и v в графе G. Метрика (V, d) является [древесная метрика|древесной]], если существует некоторое дерево T = (V', E'), такое, что <math>V \subseteq V' \;</math> и для всех <math>u, v \in V \;</math> верно <math>d_T(u, v) = d(u, v) \;</math>. Метрика (V, d) также называется метрикой, порожденной T. | ||
Пусть дана метрика (V, d); распределение D над древесной метрикой для V | Пусть дана метрика (V, d); распределение D над древесной метрикой для V ''<math>\alpha \;</math>-вероятностно аппроксимирует d'', если для каждой древесной метрики <math>d_T \in \mathcal{D} \;</math>, <math>d_T(u, v) \ge d(u, v) \;</math> и <math>E_{d_T \in D} [d_T(u, v)] \le \alpha \cdot d(u, v) \;</math> для любых <math>u, v \in V \;</math>. Значение <math>\alpha \;</math> называется [[невязка|невязкой]] аппроксимации. | ||
| Строка 30: | Строка 30: | ||
Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой O(log n) – это лучший результат по сравнению с exp(O(log nloglog n)) в [ ]. Позднее Бартал [ ], применяя тот же подход, что и Сеймур при анализе задачи о множестве обратных дуг [ ], улучшил значение невязки до O(log n log log n). Используя процедуру округления Калинеску, Карлоффа и Рабани [ ], Факчаренфол, Рао и Талвар [ ] разработали алгоритм, ожидаемо вычисляющий дерево с невязкой O(log n). Эта граница привязана к константному коэффициенту. | Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой O(log n) – это лучший результат по сравнению с exp(O(log nloglog n)) в [ ]. Позднее Бартал [ ], применяя тот же подход, что и Сеймур при анализе задачи о множестве обратных дуг [ ], улучшил значение невязки до O(log n log log n). Используя процедуру округления Калинеску, Карлоффа и Рабани [ ], Факчаренфол, Рао и Талвар [ ] разработали алгоритм, ожидаемо вычисляющий дерево с невязкой O(log n). Эта граница привязана к константному коэффициенту. | ||
== Основные результаты == | == Основные результаты == | ||
Древесная метрика тесно связана с декомпозицией графа. Рандомизированная процедура округления Калинеску, Карлоффа и Рабани [ ] для задачи 0-расширения выполняет декомпозицию графа на фрагменты ограниченного диаметра, разрезая каждое ребро с вероятностью, пропорциональной его длине и отношению между количеством вершин на определенных расстояниях. Факчаренфол, Рао и Талвар [ ] использовали эту процедуру для рекурсивной декомпозиции графа и получили следующую теорему. | Древесная метрика тесно связана с декомпозицией графа. Рандомизированная процедура округления Калинеску, Карлоффа и Рабани [ ] для задачи 0-расширения выполняет декомпозицию графа на фрагменты ограниченного диаметра, разрезая каждое ребро с вероятностью, пропорциональной его длине и отношению между количеством вершин на определенных расстояниях. Факчаренфол, Рао и Талвар [ ] использовали эту процедуру для рекурсивной декомпозиции графа и получили следующую теорему. | ||