Sciact
  • EN
  • RU

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

Journal Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN)
ISSN: 0134-4889 , E-ISSN: 2658-4786
Output data Year: 2022, Volume: 28, Number: 2, Pages: 24-44 Pages count : 21 DOI: 10.21538/0134-4889-2022-28-2-24-44
Tags 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
Authors Агеев А.А. 1 , Гимади Э.Х. 1 , Цидулко О.Ю. 1 , Штепа А.А. 2
Affiliations
1 Институт математики им. С.Л. Соболева СО РАН
2 Новосибирский государственный университет

Funding (2)

1 Sobolev Institute of Mathematics FWNF-2022-0019
2 Russian Foundation for Basic Research 20-31-90091

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(m^2n^2), 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.
Cite: Агеев А.А. , Гимади Э.Х. , Цидулко О.Ю. , Штепа А.А.
Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида
Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN). 2022. Т.28. №2. С.24-44. DOI: 10.21538/0134-4889-2022-28-2-24-44 WOS Scopus РИНЦ OpenAlex
Dates:
Published print: May 23, 2022
Identifiers:
Web of science: WOS:000905209900002
Scopus: 2-s2.0-85134827224
Elibrary: 48585943
OpenAlex: W4281648655
Citing: Пока нет цитирований
Altmetrics: