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

== Ключевые слова и синонимы ==
Встраивание метрик общего вида в древесные метрики

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


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

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

== Нотация ==
Граф 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) является [[древесная метрика|древесной]], если существует некоторое дерево <math>T = (V', E') \;</math>, такое, что <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); распределение <math>\mathcal{D} \;</math> над древесной метрикой для 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> называется [[невязка|невязкой]] аппроксимации.


Хотя в определении вероятностной аппроксимации используется распределение <math>\mathcal{D} \;</math> над древесными метриками, нам бы хотелось найти процедуру, которая строила бы метрику случайного дерева, распределенную согласно <math>\mathcal{D} \;</math>, т.е. такой алгоритм, который создавал бы метрику случайного дерева, вероятностно аппроксимирующую заданную метрику. Формальное определение задачи выглядит следующим образом.


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

Дано: метрика (V, d)

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


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


Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой <math>O(log^2 \; n)</math> – это лучший результат по сравнению с <math>exp(O(\sqrt{log \; n \; log \; log \; n }))</math> в [1]. Позднее Бартал [3], применяя тот же подход, что и Сеймур при анализе задачи о множестве обратных дуг [18], улучшил значение невязки до O(log n log log n). Используя процедуру округления Калинеску, Карлоффа и Рабани [5], Факчаренфол, Рао и Талвар [9] разработали алгоритм, ожидаемо вычисляющий дерево с невязкой O(log n). Эта граница является точной с поправкой на константный коэффициент.

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


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


Граница в теореме 1 является точной, поскольку Алон и др. [1] доказали границу невязки <math>\Omega(log \; n)</math> в случае, когда (V, d) порождается графом-решеткой. Также стоит отметить, что существует убеждение, что даже встраивание линейной метрики в 2-HST-дерево приводит к невязке <math>\Omega (log \; n)</math>.


Если дерево должно быть k-HST-деревом, можно применить результат Бартала, Чарикара и Раза [4], который заключается в том, что любое 2-HST-дерево может быть O(k/log k)-вероятностно аппроксимировано k-HST-деревом с получением ожидаемой невязки O(k log n/log k).


Задача поиска распределения древесных метрик, вероятностно аппроксимирующих заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева T с малым средним взвешенным растяжением. Более конкретно, пусть даны веса ребер <math>c_{uv} \;</math>; необходимо найти древесную метрику <math>d_T \;</math>, такую, что для всех <math>u, v \in V \;</math> верно <math>d_T(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).'''


Отметим, что дерево на выходе алгоритма содержит вершины Штейнера; однако Гупта [10] показал, как найти другую древесную метрику, не содержащую вершин Штейнера и при этом сохраняющую все расстояния с поправкой на константный коэффициент.

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


После статьи Бартала в 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>. Остается открытым вопрос, является ли эта граница точной.

== См. также ==
* [[Системы метрических задач]]
* [[Разреженные остовы графов]]

== Литература ==
1.	Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24,78-100(1995)

2.	Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, IEEE Computer Society, pp. 184-193(1996)

3.	Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 161-168. ACM Press, New York (1998)

4.	Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k-clustering in metric spaces. In:STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 11-20. ACM Press, New York (2001)

5.	Calinescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0-extension problem. In: SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 8-16. (2001)

6.	Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation  algorithms for  group  steiner trees and k-median. In: STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 114-123. ACM Press, New York (1998)

7.	Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. In: STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 494-503. ACM Press, New York (2005)

8.	Fakcharoenphol, J., Rao, S., Talwar, K.: Approximating metrics by tree metrics. SIGACT News 35,60-70 (2004)

9.	Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69,485-497 (2004)

10.	Gupta, A.: Steiner points in tree metrics don't (really) help. In: SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 220-227. (2001)

11.	Gupta, A., Hajiaghayi, M.T., Racke, H.: Oblivious network design. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 970-979.
ACM Press, New York (2006)

12.	Gupta, A., Talwar, K.: Approximating unique games. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, New York, NY, USA, pp. 99-106. ACM Press, New York (2006)

13.	Hayrapetyan, A., Swamy, C., Tardos, Ё.: Network design for information networks. In: SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 933-942. (2005)

14.	Indyk, P., Matousek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Inc., Chap. 8 (2004), To appear

15.	Karp, R.: A 2k-competitive algorithm for the circle. Manuscript (1989)

16.	Matousek, J.: Lectures on Discrete Geometry. Springer, New York (2002)

17.	Rabinovich, Y., Raz, R.: Lower bounds on the distortion of embedding finite metric spaces in graphs. Discret. Comput. Geom. 19, 79-94(1998)

18.	Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15, 281-288 (1995)