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

Bibliographie

[1] Ageev A.A., “Grafy, matritsy i prosteishaya zadacha razmescheniya”, Upravlyaemye sistemy, 1989, no. 29, 3–11 | Zbl

[2] Ageev A.A., “Polinomialnyi algoritm resheniya zadachi razmescheniya na posledovatelno-parallelnoi seti”, Upravlyaemye sistemy, 1990, no. 30, 3–16 | Zbl

[3] Ageev A.A., Gimadi E.Kh., Kurochkin A.A., “Polinomialnyi algoritm resheniya zadachi razmescheniya na tsepi s odinakovymi proizvodstvennymi moschnostyami predpriyatii”, Diskretnyi analiz i issledovanie operatsii, 16:5 (2009), 3–18 | MR | Zbl

[4] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979, 536 pp.

[5] Beresnev V.L., Gimadi E.Kh., Dementev V.T., Ekstremalnye zadachi standartizatsii, Nauka, Novosibirsk, 1978, 333 pp. | MR

[6] Voznyuk I.P., “Zadacha razmescheniya na seti s ogranichennymi propusknymi sposobnostyami kommunikatsii”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 6:1 (1999), 3–11 | MR | Zbl

[7] Voznyuk I.P., “Zadacha razmescheniya punktov proizvodstva na dva-dereve s ogranichennymi propusknymi sposobnostyami kommunikatsii”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 7:1 (2000), 3–8 | MR | Zbl

[8] Gimadi E.Kh., “Effektivnyi algoritm razmescheniya s oblastyami obsluzhivaniya, svyaznymi otnositelno atsiklicheskoi seti”, Upravlyaemye sistemy, 1983, no. 23, 12–23, Novosibirsk | Zbl

[9] Gimadi E.Kh., “Tochnyi algoritm resheniya vneshneplanarnoi zadachi razmescheniya s uluchshennoi vremennoi slozhnostyu”, Tr. In-ta matematiki i mekhaniki UrO RAN, 23:3 (2017), 74–81

[10] Trubin V.A., “Effektivnyi algoritm resheniya zadachi razmescheniya na seti v forme dereva”, Dokl. AN SSSR, 231:3 (1976), 547–550 | MR | Zbl

[11] Ageev A.A., “A Criterion of polynomial-time solvability for the network location problem”, Integer Programming and Combinatorial Optimization (Proc. IPCO II Conf. Campus Printing), Carnegi Mellon University, Pittsburg, 1992, 237–245

[12] Ageev A.A., “Complexity of the network median problem on planar grids”, Siberian Adv. Math., 5 (1995), 1–9 | MR

[13] Ageev A.A., “A polynomial-time algorithm for the facility location problem with uniform hard capacities on path graph”, Proc. of the 2-nd Intern. Workshop Discrete Optimization Methods in Production and Logistics (DOM'2004), Omsk, 2004, 28–32

[14] Aggarwal A., Klawe M.M., Moran S., Shor P., Wilber R., “Geometric applications of a matrix searching algorithm”, Algorthmica, 2 (1987), 195–208 | DOI | MR | Zbl

[15] Aggarwal A., Louis A., Bansal M. et al., “A 3-approximation algorithm for the facility location problem with uniform capacities”, Math. Programming, 141 (2013), 527–547 | DOI | MR | Zbl

[16] Bansal M., Garg N., Gupta N., “A 5-approximation algorithm for capacitated facility location”, Algorithms - ESA 2012, Lecture Notes in Computer Science, 7501, eds. L. Epstein, P. Ferragina, 2012, 133–144 | DOI | MR | Zbl

[17] Bilde O., Krarup J., “Sharp lower bounds and efficient algorithms for the simple plant location problem”, Annals Discret. Math., 1 (1977), 79–97 | DOI | MR | Zbl

[18] Billionet A., Costa M.-C., “Solving the uncapacitated plant location problem on trees”, Discret. Appl. Math., 49:1–3 (1994), 51–59 | DOI | MR

[19] Blum M., Floyd R.W., Pratt V., Rivest R.L., Tarjan E., “Time bounds for selection”, Journal of Computer and System Sciences, 7:4 (1973), 448–461 | DOI | MR | Zbl

[20] Cornuéjols G., Nemhauser G.L., Wolsey L.A., “The uncapacitated facility location problem”, Discret. Location Theory, Wiley, NY, 1990, 119–171 | MR

[21] Garey M.R., Johnson D.S., Computers and intractability: A guide to the theory of $NP$-completeness, San Francisco, 1990, 338 pp. | DOI | MR

[22] Gimadi E.Kh., Kurochkina A.A., “Time complexity of the Ageev's algorithm to solve the uniform hard capacities facility location problem”, Optimization and Applications, 9th Internat. Conf. (OPTIMA 2018), Communications in Computer and Information Science, 974, 2019 | DOI | MR

[23] Gimadi E.Kh., Tsidulko O.Yu., “On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines”, Proc. Steklov Institute Math., 313:suppl. 1 (2021), 1–15 | DOI | MR

[24] Granot D., Skorin-Kapov D., “On some optimization problems on $k$-trees and partial $k$-trees”, Discret. Appl. Math., 48:2 (1994), 129–145 | DOI | MR | Zbl

[25] Hassin R., Tamir A., “Efficient algorithms for optimization and selection on series-parallel graphs”, SIAM J. Alg. Disc. Meth., 7 (1986), 379–389 | DOI | MR | Zbl

[26] Hassin R., Tamir A., “Improved complexity bounds for location problems on the real line”, Operations Research Letters, 10:7 (1991), 395–402 | DOI | MR | Zbl

[27] Laporte G., Nickel S., Saldanha da Gama F., Location science, Springer Internat. Publ., Switzerland, 2015, 644 pp. | DOI | MR | Zbl

[28] Mirchandani P., Kohli R., Tamir A., “Capacitated location problems on a line”, Transportation Science, 30:1 (1996), 75–80 | DOI | Zbl

[29] Pal M., Tardos E., Wexler T., “Facility location with hard capacities”, Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001, 329–338 | DOI | MR

[30] Shah D., “An unified limited column generation approach for facility location problem on trees”, Ann. Oper. Research, 87 (1999), 363–382 | DOI | MR

[31] Shah R., Farach-Colton V., “Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees”, Proc. 13th Ann. ACM-SIAM Symp. on discrete algorithms (San Francisco), SODA, California, 2002, 108–115 | DOI