4430
правок
Лес Штейнера: различия между версиями
Материал из WEGA
м
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 9 промежуточных версий этого же участника) | |||
| Строка 24: | Строка 24: | ||
== Основные результаты == | == Основные результаты == | ||
Агравал, Клейн и Рави [1, 2] предложили алгоритм | Агравал, Клейн и Рави [1, 2] предложили аппроксимационный алгоритм построения леса Штейнера с коэффициентом аппроксимации 2. Точнее говоря, авторы доказали следующую теорему. | ||
'''Теорема 1. Существует алгоритм | '''Теорема 1. Существует аппроксимационный алгоритм, который для каждого экземпляра I = (G, c, R) задачи построения леса Штейнера вычисляет допустимый лес F, такой, что <math>c(F) \le \Big( 2 - \frac{1}{k} \Big) \cdot OPT(I) \;</math>, где k – количество пар полюсов в R, а OPT(I) – стоимость оптимального леса Штейнера для I.''' | ||
| Строка 47: | Строка 47: | ||
Двойственная задача для релаксации линейного программирования (IP) включает переменную <math>y_S \;</math> для каждого разреза Штейнера <math>S \in \mathcal{S} \;</math>. Существует ограничение: для каждого ребра <math>e \in E \;</math> полная двойственная задача, присвоенная множествам <math>S \in \mathcal{S} \;</math>, содержащим | Двойственная задача для релаксации линейного программирования (IP) включает переменную <math>y_S \;</math> для каждого разреза Штейнера <math>S \in \mathcal{S} \;</math>. Существует ограничение: для каждого ребра <math>e \in E \;</math> полная двойственная задача, присвоенная множествам <math>S \in \mathcal{S} \;</math>, содержащим ровно одну конечную точку e, имеет стоимость не более c(e): | ||
(D) максимизировать <math>\sum_{S \in \mathcal{S}} y_S</math> | (D) максимизировать <math>\sum_{S \in \mathcal{S}} y_S</math> | ||
| Строка 62: | Строка 62: | ||
Ребро <math>e \in E \;</math> является ''плотным'', если соответствующее ограничение (3) выполняется в виде равенства; путь является плотным, если все | Ребро <math>e \in E \;</math> является ''плотным'', если соответствующее ограничение (3) выполняется в виде равенства; путь является плотным, если все составляющие его ребра являются плотными. Пусть <math>H^{ \tau} \;</math> – подграф G, порожденный плотными ребрами для двойственного значения <math>y^{ \tau} \;</math>. Связные компоненты <math>H^{ \tau} \;</math> порождают разбиение <math>C^{ \tau} \;</math> на множестве вершин V. Пусть <math>\mathcal{S}^{ \tau} \;</math> – множество всех разрезов Штейнера, содержащихся в <math>C^{ \tau} \;</math>, т.е. <math>\mathcal{S}^{ \tau} = C^{ \tau} \cap \mathcal{S} \;</math>. Алгоритм AKR равномерно увеличивает двойственные значения <math>y_S \;</math> для всех множеств <math>S \in \mathcal{S}^{ \tau} \;</math> во все моменты времени <math>\tau \ge 0 \;</math>. Заметим, что <math>y^{ \tau} \;</math> является допустимым для двойственной задачи. Алгоритм поддерживает инвариант: <math>F^{ \tau} \;</math> в любой момент времени является подграфом <math>H^{ \tau} \;</math>. Рассмотрим событие, при котором путь P между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> в <math>F^{ \tau} \;</math> становится плотным. После этого недостающие ребра P добавляются к <math>F^{ \tau} \;</math> и процесс продолжается. В конечном итоге все деревья <math>F^{ \tau} \;</math> становятся неактивными, в результате чего процесс завершается. | ||
== Применение == | == Применение == | ||
Вычисление (приближенных) решений задачи построения леса Штейнера имеет немало теоретических и практических вариантов применения; отметим только самые недавние разработки. | Вычисление (приближенных) решений задачи построения леса Штейнера имеет немало теоретических и практических вариантов применения; отметим только самые недавние разработки. | ||
Онлайн-версии алгоритмов построения дерева и леса Штейнера изучали Авербух и др. [5], а также Берман и Коулстон [7]. В области алгоритмической теории игр разработка механизмов распределения затрат в рамках групповой стратегии для задач проектирования сетей – таких как задача построения дерева Штейнера – недавно удостоилась широкого внимания исследователей; см., например, [16, 17, 19, 20]. Адаптация алгоритма AKR позволила получить подобный механизм распределения затрат для задачи построения леса Штейнера [18]. | Алгоритмы проектирования сетей сложной конструкции нередко полагаются на качественные аппроксимационные алгоритмы построения леса Штейнера. Например, недавно опубликованные аппроксимационные алгоритмы [6, 9, 12] для задачи построения ''многопродуктовой сети покупки или аренды'' (multi-commodity rent-or-buy problem, MRoB) основаны на структуре случайной выборки Гупты и др. [12,13]. Эта структура использует аппроксимационный алгоритм построения леса Штейнера, удовлетворяющий определенному свойству строгости, заданному в виде дополнительной подпрограммы. Флейшер и др. [9] показали, что алгоритм AKR удовлетворяет этому свойству строгости, благодаря чему был разработан лучший на данный момент алгоритм 5-аппроксимации для MRoB. Свойство строгости также играет важнейшую роль в структуре выборки с усилением, предложенной Гуптой и др. [14] для задач двухступенчатой стохастической оптимизации с регрессом. | ||
Онлайн-версии алгоритмов построения дерева и леса Штейнера изучали Авербух и др. [5], а также Берман и Коулстон [7]. В области алгоритмической теории игр разработка ''механизмов распределения затрат в рамках групповой стратегии'' для задач проектирования сетей – таких как задача построения дерева Штейнера – недавно удостоилась широкого внимания исследователей; см., например, [16, 17, 19, 20]. Адаптация алгоритма AKR позволила получить подобный механизм распределения затрат для задачи построения леса Штейнера [18]. | |||
== См. также == | == См. также == | ||
* ''[[Обобщенная | * ''[[Обобщенная задача построения сети Штейнера]] | ||
* ''[[ | * ''[[Деревья Штейнера|Деревья Штейнера]] | ||
== Литература == | == Литература == | ||
Обратитесь к статьям [2, 11] за более детальным описанием прямо-двойственных алгоритмов | Обратитесь к статьям [2, 11] за более детальным описанием прямо-двойственных аппроксимационных алгоритмов для задач проектирования сетей общего вида. | ||
