4446
правок
Лес Штейнера: различия между версиями
Материал из WEGA
м
нет описания правки
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 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.''' | ||
| Строка 68: | Строка 68: | ||
Вычисление (приближенных) решений задачи построения леса Штейнера имеет немало теоретических и практических вариантов применения; отметим только самые недавние разработки. | Вычисление (приближенных) решений задачи построения леса Штейнера имеет немало теоретических и практических вариантов применения; отметим только самые недавние разработки. | ||
Алгоритмы проектирования сетей сложной конструкции нередко полагаются на качественные алгоритмы | Алгоритмы проектирования сетей сложной конструкции нередко полагаются на качественные аппроксимационные алгоритмы построения леса Штейнера. Например, недавно опубликованные аппроксимационные алгоритмы [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]. | Онлайн-версии алгоритмов построения дерева и леса Штейнера изучали Авербух и др. [5], а также Берман и Коулстон [7]. В области алгоритмической теории игр разработка ''механизмов распределения затрат в рамках групповой стратегии'' для задач проектирования сетей – таких как задача построения дерева Штейнера – недавно удостоилась широкого внимания исследователей; см., например, [16, 17, 19, 20]. Адаптация алгоритма AKR позволила получить подобный механизм распределения затрат для задачи построения леса Штейнера [18]. | ||
| Строка 79: | Строка 79: | ||
Обратитесь к статьям [2, 11] за более детальным описанием прямо-двойственных алгоритмов | Обратитесь к статьям [2, 11] за более детальным описанием прямо-двойственных аппроксимационных алгоритмов для задач проектирования сетей общего вида. | ||
