4501
правка
Аппроксимация метрических пространств древесными метриками: различия между версиями
Перейти к навигации
Перейти к поиску
Аппроксимация метрических пространств древесными метриками (посмотреть исходный код)
Версия от 11:46, 1 ноября 2016
, 1 ноября 2016→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
== Основные результаты == | == Основные результаты == | ||
Древесная метрика тесно связана с декомпозицией графа. Рандомизированная процедура округления Калинеску, Карлоффа и Рабани [ ] для задачи 0-расширения выполняет декомпозицию графа на фрагменты ограниченного диаметра, разрезая каждое ребро с вероятностью, пропорциональной его длине и отношению между количеством вершин на определенных расстояниях. Факчаренфол, Рао и Талвар [ ] использовали эту процедуру для рекурсивной декомпозиции графа и получили следующую теорему. | Древесная метрика тесно связана с декомпозицией графа. Рандомизированная процедура округления Калинеску, Карлоффа и Рабани [5] для задачи 0-расширения выполняет декомпозицию графа на фрагменты ограниченного диаметра, разрезая каждое ребро с вероятностью, пропорциональной его длине и отношению между количеством вершин на определенных расстояниях. Факчаренфол, Рао и Талвар [9] использовали эту процедуру для рекурсивной декомпозиции графа и получили следующую теорему. | ||
Теорема 1. Пусть имеется n-точечная метрика (V, d). Существует рандомизированный алгоритм, который за время O( | Теорема 1. Пусть имеется n-точечная метрика (V, d). Существует рандомизированный алгоритм, который за время <math>O(n^2) \;</math> осуществляет выборку древесной метрики из распределения <math>\mathcal{D} \;</math> над древесными метриками, которая O(log n)-вероятностно аппроксимирует (V, d). Это дерево также является 2-HST-деревом. | ||
Граница в теореме 1 является точной, поскольку Алон и др. [1] доказали границу невязки | Граница в теореме 1 является точной, поскольку Алон и др. [1] доказали границу невязки <math>\Omega(log \; n)</math> в случае, когда (V, d) порождается графом-решеткой. Также стоит отметить, что существует убеждение, что даже встраивание линейной метрики в 2-HST-дерево приводит к невязке <math>\Omega (log \; n)</math>. | ||
Если дерево должно быть k-HST-деревом, можно применить результат Бартала, Чарикара и Раза [ ], который заключается в том, что любое 2-HST-дерево может быть O(k/log k)-вероятностно аппроксимировано k-HST-деревом с получением ожидаемой невязки O( | Если дерево должно быть k-HST-деревом, можно применить результат Бартала, Чарикара и Раза [4], который заключается в том, что любое 2-HST-дерево может быть O(k/log k)-вероятностно аппроксимировано k-HST-деревом с получением ожидаемой невязки O(k log n/log k). | ||
Задача поиска распределения древесных метрик, вероятностно аппроксимирующее заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева T с малым средним взвешенным растяжением. Более конкретно, пусть даны веса ребер | Задача поиска распределения древесных метрик, вероятностно аппроксимирующее заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева T с малым средним взвешенным растяжением. Более конкретно, пусть даны веса ребер <math>c_{uv} \;</math>; необходимо найти древесную метрику <math>d_T \;</math>, такую, что для всех <math>u, v \in Vd_T \;</math> верно <math>(u, v) \ge d(u, v) \;</math> и <math>\sum_{u, v \in V} c_{uv} \cdot d_T(u, v) \le \alpha \sum_{u, v \in V} c_{uv} \cdot d(u, v) \;</math>. | ||
| Строка 56: | Строка 56: | ||
Отметим, что дерево на выходе алгоритма содержит вершины Штейнера; однако Гупта Gupta [10] показал, как найти другую древесную метрику, не содержащую вершин Штейнера и при этом сохраняющую все расстояния с поправкой на константный коэффициент. | Отметим, что дерево на выходе алгоритма содержит вершины Штейнера; однако Гупта Gupta [10] показал, как найти другую древесную метрику, не содержащую вершин Штейнера и при этом сохраняющую все расстояния с поправкой на константный коэффициент. | ||
== Применение == | == Применение == | ||
Аппроксимация метрики случайными деревьями находит применение в оперативных и распределенных вычислениях, поскольку рандомизация хорошо справляется с рассеянными объектами, а деревья легко поддерживать и обрабатывать. Алон и др. [ ] первыми использовали встраивание деревьев для получения конкурентного алгоритма решения k-серверной задачи. Бартал [ ] в своей статье отметил несколько возможных направлений: система метрических задач, распределенная подкачка, распределенная k-серверная задача, распределенная система обслуживания очередей, работа с мобильным пользователем. | Аппроксимация метрики случайными деревьями находит применение в оперативных и распределенных вычислениях, поскольку рандомизация хорошо справляется с рассеянными объектами, а деревья легко поддерживать и обрабатывать. Алон и др. [ ] первыми использовали встраивание деревьев для получения конкурентного алгоритма решения k-серверной задачи. Бартал [ ] в своей статье отметил несколько возможных направлений: система метрических задач, распределенная подкачка, распределенная k-серверная задача, распределенная система обслуживания очередей, работа с мобильным пользователем. | ||