TY - GEN
T1 - How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs
AU - Ageev, Alexander
AU - Gimadi, Edward
AU - Shtepa, Alexandr
N1 - Funding Information:
Supported by the program of fundamental scientific researches of the SB RAS (project No. 0314-2019-0014), and by the Russian Foundation for Basic Research, (project No. 20-31-90091).
Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - The Capacitated Facility Location Problem (CFLP) aims to open a subset of facilities, each of which has an opening cost and a capacity constraint, to serve all the given client demands such that the total transportation and facility opening costs are minimized. We consider the network CFLP in which the clients and the facilities are located at the vertices of a given edge-weighted transportation network graph. The network CFLP is NP-hard even when the network is a simple path. However, the Uniform CFLP (UCFLP) where the capacities of all facilities are identical is known to be polynomial-time solvable on path graphs. In this paper we revisit the dynamic programming algorithm by Ageev, Gimadi and Kurochkin [Diskret. Analys. Issl. Oper., 2009] for the UCFLP on path graphs and show how its time complexity can be improved to O(m2n2), where m is the number of possible facility locations, n is the number of clients, which is the best possible time complexity within the framework of the considered algorithm. Also we carried out the comparison of the proposed strictly polynomial algorithm with the best pseudo-polynomial algorithms.
AB - The Capacitated Facility Location Problem (CFLP) aims to open a subset of facilities, each of which has an opening cost and a capacity constraint, to serve all the given client demands such that the total transportation and facility opening costs are minimized. We consider the network CFLP in which the clients and the facilities are located at the vertices of a given edge-weighted transportation network graph. The network CFLP is NP-hard even when the network is a simple path. However, the Uniform CFLP (UCFLP) where the capacities of all facilities are identical is known to be polynomial-time solvable on path graphs. In this paper we revisit the dynamic programming algorithm by Ageev, Gimadi and Kurochkin [Diskret. Analys. Issl. Oper., 2009] for the UCFLP on path graphs and show how its time complexity can be improved to O(m2n2), where m is the number of possible facility locations, n is the number of clients, which is the best possible time complexity within the framework of the considered algorithm. Also we carried out the comparison of the proposed strictly polynomial algorithm with the best pseudo-polynomial algorithms.
KW - Comparison analysis
KW - Dynamic programming
KW - Exact algorithm
KW - Path graph
KW - Polynomial algorithm
KW - Pseudo-polynomial algorithm
KW - Time complexity
KW - Uniform Capacitated Facility Location Problem
UR - http://www.scopus.com/inward/record.url?scp=85142760137&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-16500-9_25
DO - 10.1007/978-3-031-16500-9_25
M3 - Conference contribution
AN - SCOPUS:85142760137
SN - 9783031164996
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 303
EP - 314
BT - Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers
A2 - Burnaev, Evgeny
A2 - Ivanov, Sergei
A2 - Panchenko, Alexander
A2 - Ignatov, Dmitry I.
A2 - Kuznetsov, Sergei O.
A2 - Khachay, Michael
A2 - Koltsova, Olessia
A2 - Kutuzov, Andrei
A2 - Loukachevitch, Natalia
A2 - Napoli, Amedeo
A2 - Pardalos, Panos M.
A2 - Saramäki, Jari
A2 - Savchenko, Andrey V.
A2 - Tsymbalov, Evgenii
A2 - Tutubalina, Elena
PB - Springer Science and Business Media Deutschland GmbH
T2 - 10th International Conference on Analysis of Images, Social Networks and Texts, AIST 2021
Y2 - 16 December 2021 through 18 December 2021
ER -