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

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

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

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

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

Известно, что древесные метрики плохо аппроксимируют метрики общего вида; иначе говоря, если дан цикл 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, т.е. такой алгоритм, который создавал бы метрику случайного дерева, вероятностно аппроксимирующую заданную метрику. Формальное определение задачи выглядит следующим образом.