We study the network facility location problem with constraints on the capacities of communication lines, called Restricted Facility Location Problem (RFLP). It is required to locate facilities at the vertices of a given network graph so as to simultaneously satisfy at minimum cost the demands of customers located at the vertices of the graph. We consider two statements of the problem: the multiple allocation RFLP, where the demand of a customer can be satisfied jointly by several facilities, and the single allocation RFLP, where the demand of a customer must be entirely satisfied by a single facility. We show that the single allocation RFLP is NP-hard even if the network is a simple path and strongly NP-hard if the network is a tree. The multiple allocation RFLP is weakly NP-hard on trees. For this problem, we propose a pseudopolynomial-time algorithm for the case where the network graph has constant treewidth and a linear-time algorithm for the case where the network is a simple path.
|Журнал||Proceedings of the Steklov Institute of Mathematics|
|Номер выпуска||SUPPL 1|
|Состояние||Опубликовано - авг 2021|
Предметные области OECD FOS+WOS
- 1.01 МАТЕМАТИКА