Standard

On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines. / Gimadi, E. Kh.; Tsidulko, O. Yu.

In: Proceedings of the Steklov Institute of Mathematics, Vol. 313, No. SUPPL 1, 08.2021, p. S58-S72.

Research output: Contribution to journal › Article › peer-review

Harvard

Gimadi, EK & Tsidulko, OY 2021, 'On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines', Proceedings of the Steklov Institute of Mathematics, vol. 313, no. SUPPL 1, pp. S58-S72. https://doi.org/10.1134/S0081543821030081

APA

Gimadi, E. K., & Tsidulko, O. Y. (2021). On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines. Proceedings of the Steklov Institute of Mathematics, 313(SUPPL 1), S58-S72. https://doi.org/10.1134/S0081543821030081

Vancouver

Gimadi EK, Tsidulko OY. On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines. Proceedings of the Steklov Institute of Mathematics. 2021 Aug;313(SUPPL 1):S58-S72. doi: 10.1134/S0081543821030081

Author

Gimadi, E. Kh. ; Tsidulko, O. Yu. / On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines. In: Proceedings of the Steklov Institute of Mathematics. 2021 ; Vol. 313, No. SUPPL 1. pp. S58-S72.

BibTeX

@article{5306a6ab1f714359ad6e75c769b446e3,
title = "On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines",
abstract = "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, pseudopolynomial-time algorithm, polynomial-time algorithm, UNSPLITTABLE FLOW, ALGORITHMS, TREES, PATHS",
author = "Gimadi, {E. Kh.} and Tsidulko, {O. Yu.}",
year = "2021",
month = aug,
doi = "10.1134/S0081543821030081",
language = "English",
volume = "313",
pages = "S58--S72",
journal = "Proceedings of the Steklov Institute of Mathematics",
issn = "0081-5438",
publisher = "Maik Nauka Publishing / Springer SBM",
number = "SUPPL 1",

}

RIS

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 -

ID: 29277054