## 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(m^{2}n^{2}), 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.

Original language | English |
---|---|

Title of host publication | Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers |

Editors | 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 |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 303-314 |

Number of pages | 12 |

ISBN (Print) | 9783031164996 |

DOIs | |

Publication status | Published - 2022 |

Event | 10th International Conference on Analysis of Images, Social Networks and Texts, AIST 2021 - Tbilisi, Georgia Duration: 16 Dec 2021 → 18 Dec 2021 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13217 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 10th International Conference on Analysis of Images, Social Networks and Texts, AIST 2021 |
---|---|

Country/Territory | Georgia |

City | Tbilisi |

Period | 16.12.2021 → 18.12.2021 |

## Keywords

- Comparison analysis
- Dynamic programming
- Exact algorithm
- Path graph
- Polynomial algorithm
- Pseudo-polynomial algorithm
- Time complexity
- Uniform Capacitated Facility Location Problem

## OECD FOS+WOS

- 1.02 COMPUTER AND INFORMATION SCIENCES
- 1.01 MATHEMATICS