О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций

Translated title of the contribution: 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 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.

Translated title of the contributionOn some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
Original languageRussian
Pages (from-to)108-124
Number of pages17
JournalTrudy Instituta Matematiki i Mekhaniki UrO RAN
Volume26
Issue number2
DOIs
Publication statusPublished - 25 May 2020

Keywords

  • Capacities
  • Facility location problem
  • Multiple-allocation
  • NP-hard problem
  • Polynomial-time algorithm
  • Pseudopolynomial algorithm
  • Single-allocation
  • Treewidth
  • tree-width
  • UNSPLITTABLE FLOW
  • pseudopolynomial algorithm
  • PATHS
  • ALGORITHMS
  • facility location problem
  • multiple-allocation
  • TREES
  • capacities
  • single-allocation
  • polynomial-time algorithm

State classification of scientific and technological information

  • 27 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