Лес Штейнера: различия между версиями

Алгоритмы проектирования сетей сложной конструкции нередко полагаются на качественные алгоритмы аппроксимации для леса Штейнера. Например, недавно опубликованные алгоритмы аппроксимации [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].