Обобщенная задача построения сети Штейнера: различия между версиями

Задача о создании обобщенной сети Штейнера – очень простая и естественная задача проектирования сетей, имеющая множество вариантов применения в различных областях, включая разработку сетей коммуникаций, проектирование СБИС и маршрутизацию транспорта. Одним из примеров может служить построение сетей коммуникаций с повышенной живучестью, остающихся функциональными даже после отказа некоторых компонентов сети (подробнее см. в [ ]).

Алгоритм 2-аппроксимации Джейна [ ] для обобщенной задачи построения сети Штейнера основан на LP-округлении и имеет достаточно большое время выполнения. Было бы любопытно разработать алгоритм комбинаторной аппроксимации для этой задачи.