A.A. Ageev, E.Kh. Gimadi, O.Yu. Tsidulko, A.A. Shtepa. Capacitated Facility Location Problem on tree-like graphs ... P. 24-44

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.

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

Received April 28, 2022

Revised May 16, 2022

Accepted May 20, 2022

Funding Agency: This work was supported within the State Assignment to the Institute of Mathematics of Siberian Branch of the Russian Academy of Sciences (project no. FWNF-2022-0019) and by the Russian Foundation for Basic Research (project no. 20-31-90091).

Alexander Alexandrovich Ageev, Cand. Phys.-Math. Sci., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: ageev@math.nsc.ru

Edward Khairutdinovich Gimadi, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gimadi@math.nsc.ru

Alexandr Alexandrovich Shtepa, Post-grad. student, Novosibirsk State University (NSU), Novosibirsk, 630090 Russia, e-mail: shoomath@gmail.com

Oxana Yurievna Tsidulko, Cand. Phys.-Math. Sci., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: tsidulko@math.nsc.ru

REFERENCES

1.   Ageev A.A. Graphs, matrices and an elementary location problem. Upravliaemie Systemy, 1989, no. 29, pp. 3–10 (in Russian).

2.   Ageev A.A. A polynomial algorithm for solving the location problem on a series-parallel network. Upravliaemie systemy, 1990, no. 30, pp. 3–16 (in Russian).

3.   Ageev A.A., Gimadi E.K., Kurochkin A.A. A polynomial algorithm for solving the facility location problem on a chain network with identical plant production capacities. Diskretn. Anal. Issled. Oper., 2009, vol. 16, no. 5, pp. 3–18 (in Russian).

4.   Aho A., Hopcroft J., Ullman J. The design and analysis of computer algorithms. Reading, Mass.: Addison-Wesley, 1974, 470 p. ISBN: 0201000296 . Translated to Russian under the title Postroenie i analiz vychislitel’nykh algoritmov. Moscow: Mir Publ., 1979, 536 p.

5.   Beresnev V.L., Gimadi E.Kh., Dement’ev V.T. Ekstremal’nye zadachi standartizatsii [Extremal standardization problems]. Novosibirsk: Nauka Publ., 1978, 333 p.

6.   Voznyuk I.P. The location problem on networks with bounded communication capacities. Diskret. Anal. Issled. Oper., Ser. 2, 1999, vol. 6, no. 1, pp. 3–11 (in Russian).

7.   Voznyuk I.P. Facility location problem on a two-tree with bounded communication capacities. Diskret. Anal. Issled. Oper., Ser. 2, 2000, vol. 7, no. 1, pp. 3–8 (in Russian).

8.   Gimadi E.Kh. An efficient algorithm for solving plant location problem with service regions connected with respect to an acyclic network. Upravl. Sistemy, 1983, vol. 23, pp. 12–23 (in Russian).

9.   Gimadi E.Kh. An optimal algorithm for an outerplanar facility location problem with improved time complexity. Proc. Steklov Inst. Math., 2018, vol. 303, suppl. 1, pp. 87–93. doi: 10.1134/S0081543818090092 

10.   Trubin V.A. An effective algorithm for solving the distribution problem in a network in the form of a tree. Dokl. Akad. Nauk SSSR, 1976, vol. 231, no. 3, pp. 547–550 (in Russian).

11.   Ageev A.A. A criterion of polynomial-time solvability for the network location problem. In: Integer Programming and Combinatorial Optimization. Proc. IPCO II Conf., Campus Printing. Pittsburg: Carnegie Mellon University, 1992, pp. 237–245.

12.   Ageev A.A. Complexity of the network median problem on planar grids. Sib. Adv. Math., 1995, vol. 5, no. 2, pp. 1–9.

13.   Ageev A.A. A polynomial-time algorithm for the facility location problem with uniform hard capacities on path graph. In: Proceedings of the 2-nd Intern. Workshop Discrete Optimization Methods in Production and Logistics DOM’2004. Omsk, 2004, pp. 28–32.

14.   Aggarwal A., Klawe M.M., Moran S., Shor P., Wilber R. Geometric applications of a matrix-searching algorithm. Algorithmica, 1987, vol. 2, pp. 195–208. doi: 10.1007/BF01840359 

15.   Aggarwal A., Louis A., Bansal M., Garg N., Gupta N., Gupta S., Jain S. A 3-approximation algorithm for the facility location problem with uniform capacities. Mathematical Programming, 2013, vol. 141, pp. 527–547. doi: 10.1007/s10107-012-0565-4 

16.   Bansal M., Garg N., Gupta N. A 5-approximation for capacitated facility location. In: Algorithms – ESA 2012, Lecture Notes in Computer Science, vol. 7501, Springer, 2012, pp. 133–144. doi: 10.1007/978-3-642-33090-2_13 

17.   Bilde O., Krarup J. Sharp lower bounds and efficient algorithms for the simple plant location problem. Annal. Discret. Math., 1977, vol. 1, pp. 79–97. doi: 10.1016/S0167-5060(08)70728-3 

18.   Billionnet A., Costa M. Solving the uncapacited plant location problem on trees. Discret. Appl. Math., 1994, vol. 49, no. 1–3, pp. 51–59. doi: 10.1016/0166-218X(94)90200-3 

19.   Blum M., Floyd R.W., Pratt V., Rivest R.L., Tarjan E. Time bounds for selection J. Computer and System Sci., 1973, vol. 7, no. 4, p. 448–461, doi: 10.1016/S0022-0000(73)80033-9 

20.   Cornuéjols G., Nemhauser G.L., Wolsey L.A. The uncapacitated facility location problem. In: Discrete location theory, Mirchandani P.B. and Francis R.L. (eds). NY: Wiley, 1990, pp. 119–171.

21.   Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman, 1990, 338 p.  doi: 10.5555/574848

22.   Gimadi E.K., Kurochkina A.A. Time complexity of the Ageev’s algorithm to solve the uniform hard capacities facility location problem. In: Optimization and Applications – 9th Internat. Conf., OPTIMA 2018, Y. Evtushenko et al. (eds). Communications in Computer and Information Science, vol. 974, Springer, 2019, pp. 123–130. doi: 10.1007/978-3-030-10934-9_9 

23.   Gimadi E.K., Tsidulko O.Y. On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines. Proc. Steklov Inst. Math., 2021, vol. 313, suppl. 1, pp. S58–S72. doi: 10.1134/S0081543821030081 

24.   Granot D., Skorin-Kapov D. On some optimization problems on k-trees and partial k-trees. Discr. Appl. Math., 1994, vol. 48, no. 2, pp. 129–145. doi: 10.1016/0166-218X(92)00122-3 

25.   Hassin R., Tamir A. Efficient algorithms for optimization and selection on series-parallel graphs. SIAM J. Alg. Disc. Meth., 1986, vol. 7, no. 3, pp. 379–389. doi: 10.1137/0607043 

26.   Hassin R., Tamir A. Improved complexity bounds for location problems on the real line. Operations Research Letters, 1991, vol. 10, no. 7, pp. 395–402. doi: 10.1016/0167-6377(91)90041-M 

27.   Laporte G., Nickel S., Saldanha da Gama F. Location science. Switzerland: Springer Internat. Publ., 2015, 644 p. doi: 10.1007/978-3-319-13111-5 

28.   Mirchandani P., Kohli R., Tamir A. Capacitated location problems on a line. Transportation Science, 1996, vol. 30, no. 1. doi: 10.1287/trsc.30.1.75 

29.   Pál  M., Tardos E., Wexler T. Facility location with hard capacities. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 329–338. doi: 10.1109/SFCS.2001.959907 

30.   Shaw D. A unified limited column generation approach for facility location problems on trees. Ann. Oper. Research, 1999, vol. 87, pp. 363–382. doi: 10.1023/A:1018901523519 

31.   Shah R., Farach-Colton M. Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. Proc. 13th Ann. ACM-SIAM Symp. on discrete algorithms, San Francisco, California: SODA, 2002, pp. 108–115. doi: 10.1145/545381.545395 

Cite this article as: A.A. Ageev, E.Kh. Gimadi, O.Yu. Tsidulko, A.A. Shtepa. Capacitated Facility Location Problem on tree-like graphs. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 24–44.