Geodesic
On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 2, pp. 108-124

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: facility location problem, capacities, multiple allocation, single allocation, NP-hard problem, treewidth
Mots-clés : pseudopolynomial-time algorithm, polynomial-time algorithm. 
@article{TIMM_2020_26_2_a8,
     author = {E. Kh. Gimadi and O. Yu. Tsidulko},
     title = {On {Some} {Efficiently} {Solvable} {Classes} of the {Network} {Facility} {Location} {Problem} with {Constraints} on the {Capacities} of {Communication} {Lines}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {108--124},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - O. Yu. Tsidulko
TI  - On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2020
SP  - 108
EP  - 124
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/
LA  - ru
ID  - TIMM_2020_26_2_a8
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A O. Yu. Tsidulko
%T On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
%J Trudy Instituta matematiki i mehaniki
%D 2020
%P 108-124
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/
%G ru
%F TIMM_2020_26_2_a8
E. Kh. Gimadi; O. Yu. Tsidulko. On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 2, pp. 108-124. http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/