Capacitated Facility Location Problem on tree-like graphs

A. A. Ageev ; E. Kh. Gimadi ; O. Yu. Tsidulko ; A. A. Shtepa

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 24-44

Résumé

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 $\mathcal{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 $\mathcal 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 $\mathcal O(mB)$, where $B$ is the total demand of the clients.

Détail

Keywords: Capacitated Facility Location Problem, Uniform Capacitated Facility Location Problem, NP-hard problem, star graph, path graph, dynamic programming.
Mots-clés : polynomial time algorithm, pseudo-polynomial time algorithm