TY - JOUR

T1 - On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines

AU - Gimadi, E. Kh.

AU - Tsidulko, O. Yu.

PY - 2021/8

Y1 - 2021/8

N2 - 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.

AB - 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.

KW - facility location problem

KW - capacities

KW - multiple allocation

KW - single allocation

KW - NP-hard problem

KW - treewidth

KW - pseudopolynomial-time algorithm

KW - polynomial-time algorithm

KW - UNSPLITTABLE FLOW

KW - ALGORITHMS

KW - TREES

KW - PATHS

U2 - 10.1134/S0081543821030081

DO - 10.1134/S0081543821030081

M3 - Article

VL - 313

SP - S58-S72

JO - Proceedings of the Steklov Institute of Mathematics

JF - Proceedings of the Steklov Institute of Mathematics

SN - 0081-5438

IS - SUPPL 1

ER -