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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)S58-S72
Number of pages15
JournalProceedings of the Steklov Institute of Mathematics
Volume313
Issue numberSUPPL 1
DOIs
Publication statusPublished - Aug 2021

Keywords

  • facility location problem
  • capacities
  • multiple allocation
  • single allocation
  • NP-hard problem
  • treewidth
  • pseudopolynomial-time algorithm
  • polynomial-time algorithm
  • UNSPLITTABLE FLOW
  • ALGORITHMS
  • TREES
  • PATHS

OECD FOS+WOS

  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines'. Together they form a unique fingerprint.

Cite this