Аппроксимация метрических пространств древесными метриками

Ключевые слова и синонимы

Встраивание метрик общего вида в древесные метрики

Постановка задачи

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

Известно, что древесные метрики плохо аппроксимируют метрики общего вида; иначе говоря, если дан цикл Cn с n вершинами, то любая древесная метрика, аппроксимирующая эту графовую метрику, имеет невязку Q{n) [17]. Однако Карп [ ] заметил, что случайное остовное дерево Cn довольно неплохо аппроксимирует расстояния между двумя вершинами в Cn. Позднее Алон, Карп, Пелег и Уэст [ ] доказали, что граница средней невязки для аппроксимация любой графовой метрики ее остовным деревом составляет exp(O(log n log log n)).

Бартал [2] дал формальное определение понятию вероятностной аппроксимации.

Нотация

Граф G = (V, E), ребрам которого присвоены неотрицательные веса, определяет метрическое пространство (V, dG) где для каждой пары вершин u, v 2 V за dG(u, v) обозначается расстояние по кратчайшему пути между u и v в графе G. Метрика (V, d) является древесной, если существует некоторое дерево T = (V0, E0), такое, что V Q V0 и для всех u, v 2 V верно dT(u, v) = d(u, v). Метрика (V, d) также называется метрикой, порожденной T.

Пусть дана метрика (V, d); распределение D над древесной метрикой для V a-вероятностно аппроксимирует d, если каждая древесная метрика d T 2D, dT(u, v) > d(u, v) и EdT2D[dT(u, v)] < a ■ d(u, v) для любых u, v 2 V. Значение «a» называется невязкой аппроксимации.

Хотя в определении вероятностной аппроксимации используется распределение 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). Эта граница привязана к константному коэффициенту.

Основные результаты

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