Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида 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 |
|
||||
Affiliations |
|
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
Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида
Труды Института математики и механики УрО РАН (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:
Пока нет цитирований