Эффективные алгоритмы для решения многоэтапной задачи размещения на цепи

Для $NP$-трудной многоэтапной сетевой задачи размещения построены алгоритмы решения в случае сети, представляющей собой цепь. Показано, что существует оптимальное решение рассматриваемой задачи (МЗРЦ) с совокупностью согласованно-связных областей обслуживания. Показано также, что в отличие от обычной (одноуровневой, простейшей) задачи размещения оптимального решения МРЗЦ с совокупностью центральных областей обслуживания может не существовать. Один из предложенных алгоритмов имеет полиномиальную оценку временной сложности, а другой (будучи неполиномиален в случае произвольного числа этапов) более эффективен для двух- и трехэтапной задач.
Библиогр. 18