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

Материал из WEGA
Перейти к навигации Перейти к поиску
мНет описания правки
 
(не показано 14 промежуточных версий этого же участника)
Строка 3: Строка 3:


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




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


   
   
Строка 15: Строка 15:




Пусть дана метрика (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> называется [[невязка|невязкой]] аппроксимации.
Пусть дана метрика (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> называется [[невязка|невязкой]] аппроксимации.




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


Требуется: построить древесную метрику <math>(V, d_T) \;</math>, выбранную из распределения <math>\mathcal{D} \;</math> над древесными метриками, которая a-вероятностно аппроксимирует (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 раз. Эти свойства важны для многих алгоритмов аппроксимации.
Впоследствии Бартал определил класс древесных метрик, названных вполне разделенными иерархически деревьями (hierarchically well-separated trees, HST), следующим образом. ''Вполне разделенное k-иерархическое дерево'' (k-HST) представляет собой корневое взвешенное дерево, обладающее следующими двумя свойствами: веса ребер, ведущих от любой вершины к ее потомкам, равны; веса ребер на любом пути от вершины к листу уменьшаются не менее чем в k раз. Эти свойства важны для многих аппроксимационных алгоритмов.




Строка 46: Строка 46:




Задача поиска распределения древесных метрик, вероятностно аппроксимирующее заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева 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>.
Задача поиска распределения древесных метрик, вероятностно аппроксимирующих заданную метрику, имеет двойственную задачу, заключающуюся в поиске дерева 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] и независимо от этого – в работе Бартала.
Чарикар, Чекури, Гель, Гуха и Плоткин [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).'''
'''Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение <math>\mathcal{D} \;</math> над O(n log n) древесных метрик, O(log n)-вероятностно аппроксимирующее (V, d).'''




Строка 61: Строка 61:




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




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


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


== См. также ==
== См. также ==

Текущая версия от 13:21, 1 октября 2023

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

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

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

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


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