Аппроксимация метрических пространств древесными метриками: различия между версиями

Задача заключается в построении метрики случайного дерева, достаточно хорошо вероятностно аппроксимирующей заданную произвольную метрику. Решение этой задачи применяется в качестве первого этапа выполнения многочисленных алгоритмов аппроксимации, поскольку решать задачи на деревьях обычно проще, чем на графах общего вида. Кроме того, оно применяется в оперативных и распределенных вычислениях.

Известно, что древесные метрики плохо аппроксимируют метрики общего вида; иначе говоря, если дан цикл <math>C_n \;</math> с n вершинами, то любая древесная метрика, аппроксимирующая эту графовую метрику, имеет невязку <math>\Omega (n) \;</math> [17]. Однако Карп [15] заметил, что случайное остовное дерево <math>C_n \;</math> довольно неплохо аппроксимирует расстояния между двумя вершинами в <math>C_n \;</math>. Позднее Алон, Карп, Пелег и Уэст [1] доказали, что граница средней невязки при аппроксимации любой графовой метрики ее остовным деревом составляет <math>exp(O(\sqrt{log \; n \; log \; log \; n }))</math>.

Граф 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 ''<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> называется [[невязка|невязкой]] аппроксимации.

Хотя в определении вероятностной аппроксимации используется распределение D над древесными метриками, нам бы хотелось найти процедуру, которая строила бы метрику случайного дерева, распределенную согласно D, т.е. такой алгоритм, который создавал бы метрику случайного дерева, вероятностно аппроксимирующую заданную метрику. Формальное определение задачи выглядит следующим образом.

Задача (дерево аппроксимации)

Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой O(log n) – это лучший результат по сравнению с exp(O(log nloglog n)) в [ ]. Позднее Бартал [ ], применяя тот же подход, что и Сеймур при анализе задачи о множестве обратных дуг [ ], улучшил значение невязки до O(log n log log n). Используя процедуру округления Калинеску, Карлоффа и Рабани [ ], Факчаренфол, Рао и Талвар [ ] разработали алгоритм, ожидаемо вычисляющий дерево с невязкой O(log n). Эта граница привязана к константному коэффициенту.

Древесная метрика тесно связана с декомпозицией графа. Рандомизированная процедура округления Калинеску, Карлоффа и Рабани [ ] для задачи 0-расширения выполняет декомпозицию графа на фрагменты ограниченного диаметра, разрезая каждое ребро с вероятностью, пропорциональной его длине и отношению между количеством вершин на определенных расстояниях. Факчаренфол, Рао и Талвар [ ] использовали эту процедуру для рекурсивной декомпозиции графа и получили следующую теорему.

Теорема 1. Пусть имеется n-точечная метрика (V, d). Существует рандомизированный алгоритм, который за время O(n2) осуществляет выборку древесной метрики из распределения D над древесными метриками, которая O(log n)-вероятностно аппроксимирует (V, d). Это дерево также является 2-HST-деревом.

Граница в теореме 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] показал, как найти другую древесную метрику, не содержащую вершин Штейнера и при этом сохраняющую все расстояния с поправкой на константный коэффициент.

Аппроксимация метрики случайными деревьями находит применение в оперативных и распределенных вычислениях, поскольку рандомизация хорошо справляется с рассеянными объектами, а деревья легко поддерживать и обрабатывать. Алон и др. [ ] первыми использовали встраивание деревьев для получения конкурентного алгоритма решения k-серверной задачи. Бартал [ ] в своей статье отметил несколько возможных направлений: система метрических задач, распределенная подкачка, распределенная k-серверная задача, распределенная система обслуживания очередей, работа с мобильным пользователем.

 

Если имеется метрика, порожденная графом, то некоторым практическим приложениям (таким как решение определенного класса линейных систем) требуется не просто древесная метрика, а древесная метрика, порожденная остовным деревом графа. Элкин, Эмек, Спилмен и Тенг [7] предложили алгоритм поиска остовного дерева со средней невязкой O(log n log log n). Остается открытым вопрос, является ли эта граница точной.