TY - JOUR

T1 - On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines

AU - Gimadi, Edward Khairutdinovich

AU - Tsidulko, Oxana Yurievna

PY - 2020/2/1

Y1 - 2020/2/1

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 the demands of the clients, which are also located at the vertices of the network graph, at minimum cost. We consider two statements of the problem: the multiple-allocation RFLP, where the demand of a client can be satisfied jointly by several facilities, and the single-allocation RFLP, where the demand of a client 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 multipleallocation RFLP is weakly NP-hard on trees. For this problem we propose a pseudopolynomial algorithm for the case where the network graph has constant treewidth, and show 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 the demands of the clients, which are also located at the vertices of the network graph, at minimum cost. We consider two statements of the problem: the multiple-allocation RFLP, where the demand of a client can be satisfied jointly by several facilities, and the single-allocation RFLP, where the demand of a client 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 multipleallocation RFLP is weakly NP-hard on trees. For this problem we propose a pseudopolynomial algorithm for the case where the network graph has constant treewidth, and show a linear-time algorithm for the case where the network is a simple path.

KW - Capacities

KW - Facility location problem

KW - Multiple-allocation

KW - NP-hard problem

KW - Polynomial-time algorithm

KW - Pseudopolynomial algorithm

KW - Single-allocation

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85090526044&partnerID=8YFLogxK

UR - https://www.elibrary.ru/item.asp?id=42950652

U2 - 10.21538/0134-4889-2020-26-2-108-124

DO - 10.21538/0134-4889-2020-26-2-108-124

M3 - Article

AN - SCOPUS:85090526044

VL - 26

SP - 108

EP - 124

JO - Trudy Instituta Matematiki i Mekhaniki UrO RAN

JF - Trudy Instituta Matematiki i Mekhaniki UrO RAN

SN - 0134-4889

IS - 2

ER -