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

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

Требуется: построить древесную метрику <math>(V, d_T) \;</math>, выбранную из распределения <math>\mathcal{D} \;</math> над древесными метриками, которая a-вероятностно аппроксимирует (V, d).

Впоследствии Бартал определил класс древесных метрик, названных вполне разделенными иерархически деревьями (hierarchically well-separated trees, HST), следующим образом. ''Вполне разделенное k-иерархическое дерево'' (k-HST) представляет собой корневое взвешенное дерево, обладающее следующими двумя свойствами: веса ребер, ведущих от любой вершины к ее потомкам, равны; веса ребер на любом пути от вершины к листу уменьшаются не менее чем в k раз. Эти свойства важны для многих алгоритмов аппроксимации.

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

Чарикар, Чекури, Гель, Гуха и Плоткин [6] показали, как найти распределение O(n log n) древесных метрик, <math>\alpha \;</math>-вероятностно аппроксимирующее заданную метрику, при условии возможности решения двойственной задачи. Алгоритм теоремы 1 может быть дерандомизирован при помощи метода с использованием условного матожидания, что дает в результате требуемую древесную метрику <math>\alpha = O(log \; n)</math>. Еще один алгоритм, основанный на модификации техники наращивания областей, был представлен в [9] и независимо от этого – в работе Бартала.

'''Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение <math>\mathcal{D} \;</math> над O(n log n) древесных метрик, которая O(log n)-вероятностно аппроксимирует (V, d).'''

После статьи Бартала в 1996 году было найдено множество применений алгоритмов аппроксимации. Многие из них позволяют решать задачи на древесных метриках или HST-метриках. Аппроксимируя метрики общего вида при помощи этих метрик, можно превратить их в алгоритмы для метрик общего вида, как правило, с потерей только члена O(log n) в коэффициенте аппроксимации. Среди примеров подобного подхода можно упомянуть разметку при помощи метрики, построение сетей с применением «оптового» подхода и группировку деревьев Штейнера. Среди новых областей применения стоит отметить алгоритм аппроксимации для Unique Games [12], проектирование информационных сетей [13] и сетей с рассеянной маршрутизацией [11].

Статья в SIGACT News [8] представляет обзор метрической аппроксимации при помощи древесных метрик и более детальное обсуждение построения алгоритмов и техник. См. другие примеры применения в [3, 9].

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