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

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

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

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

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

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

Применение

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

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

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

Открытые вопросы

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

См. также

• Системы метрических задач
• Разреженные остовы графов

Литература

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)