Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида

Translated title of the contribution: CAPACITATED FACILITY LOCATION PROBLEM ON TREE-LIKE GRAPHS

Alexander Alexandrovich Ageev, Edward Khairutdinovich Gimadi, O. Yu Tsidulko, Alexandr Alexandrovich Shtepa

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the network Capacitated Facility Location Problem (CFLP) and its special case - the Uniform Capacitated Facility Location Problem (UCFLP), where all facilities have the same capacity. We show that the UCFLP on a star graph is linear-time solvable if every vertex of the star can be either a facility or a client but not both. We further prove that the UCFLP on a star graph is NP-hard if the facilities and clients can be located at each vertex of the graph. The UCFLP on a path graph is known to be polynomially solvable. We give a version of the known dynamic programming algorithm for this problem with the improved time complexity O(m2n2), where m is the number of facilities and n is the number of clients. For the CFLP on a path graph we propose a pseudo-polynomial time algorithm based on the work of Mirchandani et al. (1996) with improved time complexity O(mB), where B is the total demand of the clients.

Translated title of the contributionCAPACITATED FACILITY LOCATION PROBLEM ON TREE-LIKE GRAPHS
Original languageRussian
Article number2
Pages (from-to)24-44
Number of pages21
JournalTrudy Instituta Matematiki i Mekhaniki UrO RAN
Volume28
Issue number2
DOIs
Publication statusPublished - 2022

Keywords

  • Capacitated Facility Location Problem
  • dynamic programming
  • NP-hard problem
  • path graph polynomial time algorithm
  • pseudo-polynomial time algorithm
  • star graph
  • Uniform Capacitated Facility Location Problem

OECD FOS+WOS

  • 1.01 MATHEMATICS

State classification of scientific and technological information

  • 27 MATHEMATICS

Fingerprint

Dive into the research topics of 'CAPACITATED FACILITY LOCATION PROBLEM ON TREE-LIKE GRAPHS'. Together they form a unique fingerprint.

Cite this