4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 19 промежуточных версий этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача заключается в построении метрики случайного дерева, | Задача заключается в построении метрики случайного дерева, вероятностно аппроксимирующей заданную произвольную метрику достаточно хорошим образом. Решение этой задачи применяется в качестве первого этапа выполнения многочисленных аппроксимационных алгоритмов, поскольку решать задачи на деревьях обычно проще, чем на графах общего вида. Кроме того, оно применяется в оперативных и распределенных вычислениях. | ||
Известно, что древесные метрики плохо аппроксимируют метрики общего вида; иначе говоря, если дан цикл <math>C_n \;</math> с n вершинами, то любая древесная метрика, аппроксимирующая эту графовую метрику, имеет невязку <math>\Omega (n) \;</math> [17]. Однако Карп [15] заметил, что случайное остовное дерево <math>C_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> | Пусть дана метрика (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> над древесными метриками, которая | Требуется: построить древесную метрику <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 раз. Эти свойства важны для многих аппроксимационных алгоритмов. | ||
Бартал показал, что любая метрика на n точках может быть вероятностно аппроксимирована множеством k-HST-деревьев с невязкой <math>O(log^2 \; n)</math> – это лучший результат по сравнению с exp(O(log | Бартал показал, что любая метрика на 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). Эта граница является точной с поправкой на константный коэффициент. | ||
== Основные результаты == | == Основные результаты == | ||
Древесная метрика тесно связана с декомпозицией графа. Рандомизированная процедура округления Калинеску, Карлоффа и Рабани [ ] для задачи 0-расширения выполняет декомпозицию графа на фрагменты ограниченного диаметра, разрезая каждое ребро с вероятностью, пропорциональной его длине и отношению между количеством вершин на определенных расстояниях. Факчаренфол, Рао и Талвар [ ] использовали эту процедуру для рекурсивной декомпозиции графа и получили следующую теорему. | Древесная метрика тесно связана с декомпозицией графа. Рандомизированная процедура округления Калинеску, Карлоффа и Рабани [5] для задачи 0-расширения выполняет декомпозицию графа на фрагменты ограниченного диаметра, разрезая каждое ребро с вероятностью, пропорциональной его длине и отношению между количеством вершин на определенных расстояниях. Факчаренфол, Рао и Талвар [9] использовали эту процедуру для рекурсивной декомпозиции графа и получили следующую теорему. | ||
Теорема 1. Пусть имеется n-точечная метрика (V, d). Существует рандомизированный алгоритм, который за время O( | '''Теорема 1. Пусть имеется n-точечная метрика (V, d). Существует рандомизированный алгоритм, который за время <math>O(n^2) \;</math> осуществляет выборку древесной метрики из распределения <math>\mathcal{D} \;</math> над древесными метриками, которая O(log n)-вероятностно аппроксимирует (V, d). Это дерево также является 2-HST-деревом.''' | ||
Граница в теореме 1 является точной, поскольку Алон и др. [1] доказали границу невязки | Граница в теореме 1 является точной, поскольку Алон и др. [1] доказали границу невязки <math>\Omega(log \; n)</math> в случае, когда (V, d) порождается графом-решеткой. Также стоит отметить, что существует убеждение, что даже встраивание линейной метрики в 2-HST-дерево приводит к невязке <math>\Omega (log \; n)</math>. | ||
Если дерево должно быть k-HST-деревом, можно применить результат Бартала, Чарикара и Раза [ ], который заключается в том, что любое 2-HST-дерево может быть O(k/log k)-вероятностно аппроксимировано k-HST-деревом с получением ожидаемой невязки O( | Если дерево должно быть 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) древесных метрик, | Чарикар, Чекури, Гель, Гуха и Плоткин [6] показали, как найти распределение O(n log n) древесных метрик, <math>\alpha \;</math>-вероятностно аппроксимирующее заданную метрику, при условии возможности решения двойственной задачи. Алгоритм теоремы 1 может быть дерандомизирован при помощи метода с использованием условного матожидания, что дает в результате требуемую древесную метрику при <math>\alpha = O(log \; n)</math>. Еще один алгоритм, основанный на модификации техники наращивания областей, был представлен в [9] и независимо от этого – в работе Бартала. | ||
Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение D над O( | '''Теорема 2. Пусть имеется n-точечная метрика (V, d). Существует детерминированный алгоритм с полиномиальным временем выполнения, который находит распределение <math>\mathcal{D} \;</math> над O(n log n) древесных метрик, O(log n)-вероятностно аппроксимирующее (V, d).''' | ||
Отметим, что дерево на выходе алгоритма содержит вершины Штейнера; однако Гупта | Отметим, что дерево на выходе алгоритма содержит вершины Штейнера; однако Гупта [10] показал, как найти другую древесную метрику, не содержащую вершин Штейнера и при этом сохраняющую все расстояния с поправкой на константный коэффициент. | ||
== Применение == | == Применение == | ||
Аппроксимация метрики случайными деревьями находит применение в оперативных и распределенных вычислениях, поскольку рандомизация хорошо справляется с рассеянными объектами, а деревья легко поддерживать и обрабатывать. Алон и др. [ ] первыми использовали встраивание деревьев для получения конкурентного алгоритма решения k-серверной задачи. Бартал [ ] в своей статье отметил несколько возможных направлений: система метрических задач, распределенная подкачка, распределенная k-серверная задача, распределенная система обслуживания очередей, работа с мобильным пользователем. | Аппроксимация метрики случайными деревьями находит применение в оперативных и распределенных вычислениях, поскольку рандомизация хорошо справляется с рассеянными объектами, а деревья легко поддерживать и обрабатывать. Алон и др. [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>. Остается открытым вопрос, является ли эта граница точной. | ||
== См. также == | == См. также == |
правок