4511
правок
Лес Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 68: | Строка 68: | ||
Вычисление (приближенных) решений задачи построения леса Штейнера имеет немало теоретических и практических вариантов применения; отметим только самые недавние разработки. | Вычисление (приближенных) решений задачи построения леса Штейнера имеет немало теоретических и практических вариантов применения; отметим только самые недавние разработки. | ||
Алгоритмы проектирования сетей сложной конструкции нередко полагаются на качественные алгоритмы аппроксимации для леса Штейнера. Например, недавно опубликованные алгоритмы аппроксимации [6, 9, 12] для задачи построения многопродуктовой сети покупки или аренды (multi-commodity rent-or-buy problem, MRoB) основаны на структуре случайной выборки Гупты и др. [12,13]. Эта структура использует алгоритм аппроксимации леса Штейнера, удовлетворяющий определенному свойству строгости, заданному в виде дополнительной подпрограммы. Флейшер и др. [9] показали, что алгоритм AKR удовлетворяет этому свойству строгости, благодаря чему был разработан лучший на данный момент алгоритм 5-аппроксимации для MRoB. Свойство строгости также играет важнейшую роль в структуре выборки с усилением, предложенной Гуптой и др. [14] для задач двухступенчатой стохастической оптимизации с регрессом. | Алгоритмы проектирования сетей сложной конструкции нередко полагаются на качественные алгоритмы аппроксимации для леса Штейнера. Например, недавно опубликованные алгоритмы аппроксимации [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]. | |||
== См. также == | == См. также == | ||