Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида

В данной работе рассматриваются сетевая задача размещения с ограничениями на объемы производства предприятий (CFLP) и ее однородный вариант (UCFLP), в котором объемы производства всех предприятий одинаковые. Мы показываем, что UCFLP на звезде решается за линейное время, если в одной вершине графа не могут одновременно находиться предприятие и клиент, и $\mathcal{NP}$-трудна, если в каждой вершине могут находиться и предприятие, и клиент. Известно, что задача UCFLP на цепи полиномиально разрешима, мы улучшаем известную схему динамического программирования для этой задачи до оценки $\mathcal O(m^2n^2)$, где $m$ — количество предприятий, $n$ — количество клиентов. Для CFLP на цепи мы предлагаем псевдополиномиальный алгоритм ее решения на основе подхода из работы Мирчандани и др. (1996) с улучшенной временной сложностью $\mathcal O(mB)$, где $B$ — суммарный спрос клиентов.