Standard
How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs. / Ageev, Alexander; Gimadi, Edward; Shtepa, Alexandr.
Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. ed. / Evgeny Burnaev; Sergei Ivanov; Alexander Panchenko; Dmitry I. Ignatov; Sergei O. Kuznetsov; Michael Khachay; Olessia Koltsova; Andrei Kutuzov; Natalia Loukachevitch; Amedeo Napoli; Panos M. Pardalos; Jari Saramäki; Andrey V. Savchenko; Evgenii Tsymbalov; Elena Tutubalina. Springer Science and Business Media Deutschland GmbH, 2022. p. 303-314 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13217 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Ageev, A
, Gimadi, E & Shtepa, A 2022,
How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs. in E Burnaev, S Ivanov, A Panchenko, DI Ignatov, SO Kuznetsov, M Khachay, O Koltsova, A Kutuzov, N Loukachevitch, A Napoli, PM Pardalos, J Saramäki, AV Savchenko, E Tsymbalov & E Tutubalina (eds),
Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13217 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 303-314, 10th International Conference on Analysis of Images, Social Networks and Texts, AIST 2021, Tbilisi, Georgia,
16.12.2021.
https://doi.org/10.1007/978-3-031-16500-9_25APA
Ageev, A.
, Gimadi, E., & Shtepa, A. (2022).
How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs. In E. Burnaev, S. Ivanov, A. Panchenko, D. I. Ignatov, S. O. Kuznetsov, M. Khachay, O. Koltsova, A. Kutuzov, N. Loukachevitch, A. Napoli, P. M. Pardalos, J. Saramäki, A. V. Savchenko, E. Tsymbalov, & E. Tutubalina (Eds.),
Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers (pp. 303-314). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13217 LNCS). Springer Science and Business Media Deutschland GmbH.
https://doi.org/10.1007/978-3-031-16500-9_25Vancouver
Ageev A
, Gimadi E, Shtepa A.
How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs. In Burnaev E, Ivanov S, Panchenko A, Ignatov DI, Kuznetsov SO, Khachay M, Koltsova O, Kutuzov A, Loukachevitch N, Napoli A, Pardalos PM, Saramäki J, Savchenko AV, Tsymbalov E, Tutubalina E, editors, Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2022. p. 303-314. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-16500-9_25
Author
Ageev, Alexander
; Gimadi, Edward ; Shtepa, Alexandr. /
How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs. Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. editor / Evgeny Burnaev ; Sergei Ivanov ; Alexander Panchenko ; Dmitry I. Ignatov ; Sergei O. Kuznetsov ; Michael Khachay ; Olessia Koltsova ; Andrei Kutuzov ; Natalia Loukachevitch ; Amedeo Napoli ; Panos M. Pardalos ; Jari Saramäki ; Andrey V. Savchenko ; Evgenii Tsymbalov ; Elena Tutubalina. Springer Science and Business Media Deutschland GmbH, 2022. pp. 303-314 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{2da2db58bbbc44838464ac7f53b5b223,
title = "How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs",
abstract = "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.",
keywords = "Comparison analysis, Dynamic programming, Exact algorithm, Path graph, Polynomial algorithm, Pseudo-polynomial algorithm, Time complexity, Uniform Capacitated Facility Location Problem",
author = "Alexander Ageev and Edward Gimadi and Alexandr Shtepa",
note = "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: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 10th International Conference on Analysis of Images, Social Networks and Texts, AIST 2021 ; Conference date: 16-12-2021 Through 18-12-2021",
year = "2022",
doi = "10.1007/978-3-031-16500-9_25",
language = "English",
isbn = "9783031164996",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "303--314",
editor = "Evgeny Burnaev and Sergei Ivanov and Alexander Panchenko and Ignatov, {Dmitry I.} and Kuznetsov, {Sergei O.} and Michael Khachay and Olessia Koltsova and Andrei Kutuzov and Natalia Loukachevitch and Amedeo Napoli and Pardalos, {Panos M.} and Jari Saram{\"a}ki and Savchenko, {Andrey V.} and Evgenii Tsymbalov and Elena Tutubalina",
booktitle = "Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers",
address = "Germany",
}
RIS
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
UR - https://www.mendeley.com/catalogue/b907b42d-e2a1-3439-b6e9-e49a47ae33af/
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 -
