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

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

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

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

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

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

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

Нотация

Граф G = (V, E), ребрам которого присвоены неотрицательные веса, определяет метрическое пространство [math]\displaystyle{ (V, d_G) \; }[/math], где для каждой пары вершин [math]\displaystyle{ u, v \in V \; }[/math] за [math]\displaystyle{ d_G(u, v) \; }[/math] обозначается расстояние по кратчайшему пути между u и v в графе G. Метрика (V, d) является древесной, если существует некоторое дерево [math]\displaystyle{ T = (V', E') \; }[/math], такое, что [math]\displaystyle{ V \subseteq V' \; }[/math] и для всех [math]\displaystyle{ u, v \in V \; }[/math] верно [math]\displaystyle{ d_T(u, v) = d(u, v) \; }[/math]. Метрика (V, d) также называется метрикой, порожденной T.

Пусть дана метрика (V, d); распределение [math]\displaystyle{ \mathcal{D} \; }[/math] над древесной метрикой для V [math]\displaystyle{ \alpha \; }[/math]-вероятностно аппроксимирует d, если для каждой древесной метрики [math]\displaystyle{ d_T \in \mathcal{D} \; }[/math] верно [math]\displaystyle{ d_T(u, v) \ge d(u, v) \; }[/math] и [math]\displaystyle{ E_{d_T \in D} [d_T(u, v)] \le \alpha \cdot d(u, v) \; }[/math] для любых [math]\displaystyle{ u, v \in V \; }[/math]. Значение [math]\displaystyle{ \alpha \; }[/math] называется невязкой аппроксимации.

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

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

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

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

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

Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой [math]\displaystyle{ O(log^2 \; n) }[/math] – это лучший результат по сравнению с [math]\displaystyle{ 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]\displaystyle{ O(n^2) \; }[/math] осуществляет выборку древесной метрики из распределения [math]\displaystyle{ \mathcal{D} \; }[/math] над древесными метриками, которая O(log n)-вероятностно аппроксимирует (V, d). Это дерево также является 2-HST-деревом.

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

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

Задача поиска распределения древесных метрик, вероятностно аппроксимирующих заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева T с малым средним взвешенным растяжением. Более конкретно, пусть даны веса ребер [math]\displaystyle{ c_{uv} \; }[/math]; необходимо найти древесную метрику [math]\displaystyle{ d_T \; }[/math], такую, что для всех [math]\displaystyle{ u, v \in V \; }[/math] верно [math]\displaystyle{ d_T(u, v) \ge d(u, v) \; }[/math] и [math]\displaystyle{ \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]\displaystyle{ \alpha \; }[/math]-вероятностно аппроксимирующее заданную метрику, при условии возможности решения двойственной задачи. Алгоритм теоремы 1 может быть дерандомизирован при помощи метода с использованием условного матожидания, что дает в результате требуемую древесную метрику при [math]\displaystyle{ \alpha = O(log \; n) }[/math]. Еще один алгоритм, основанный на модификации техники наращивания областей, был представлен в [9] и независимо от этого – в работе Бартала.

Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение [math]\displaystyle{ \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]\displaystyle{ 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)