We study the network facility location problem with constraints on the capacities of communication lines, called Restricted Facility Location Problem (RFLP). It is required to locate facilities at the vertices of a given network graph so as to simultaneously satisfy the demands of the clients, which are also located at the vertices of the network graph, at minimum cost. We consider two statements of the problem: the multiple-allocation RFLP, where the demand of a client can be satisfied jointly by several facilities, and the single-allocation RFLP, where the demand of a client must be entirely satisfied by a single facility. We show that the single-allocation RFLP is NP-hard even if the network is a simple path and strongly NP-hard if the network is a tree. The multiple-allocation RFLP is weakly NP-hard on trees. For this problem we propose a pseudopolynomial algorithm for the case where the network graph has constant treewidth, and show a linear-time algorithm for the case where the network is a simple path.
Keywords: facility location problem, capacities, single-allocation, multiple-allocation, NP-hard problem, treewidth, pseudopolynomial algorithm, polynomial-time algorithm
Received March 24, 2020
Revised May 14, 2020
Accepted May 18, 2020
Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 18-31-00470) and partially supported by Mathematical Center in Akademgorodok (agreement with Ministry of Science and High Education of the Russian Federation no. 075-15-2019-1675).
Edward Khairutdinovich Gimadi, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: gimadi@math.nsc.ru
Oxana Yurievna Tsidulko, Cand. Sci. (Phys.-Math), Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: tsidulko@math.nsc.ru
REFERENCES
1. Adamaszek A., Chalermsook P., Ene A., Wiese A. Submodular unsplittable flow on trees. Math. Program. 2018, vol. 172, pp. 565–589. doi: 10.1007/s10107-017-1218-4
2. 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. Pittsburgh: Carnegie Mellon University, 1992, pp. 237–245.
3. Andreev K., Garrod C., Golovin D., Maggs B., Meyerson A. Simultaneous source location. ACM Trans. Algorithms, 2010, vol. 6, no. 1, pp. 16:1–16:17. doi: 10.1145/1644015.1644031
4. Arata K., Iwata S., Makino K., Fujishige S. Locating sources to meet flow demands in undirected networks. J. Algorithms, 2002, vol. 42, pp. 54–68. doi: 10.1006/jagm.2001.1203
5. Bender M. A., Farach-Colton M. The LCA problem revisited. 4th Latin American Symposium on Theoretical Informatics (LATIN). 2000, LNCS; vol. 1776, pp. 88–94. doi: 10.1007/10719839_9
6. Bodlaender H. L. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. on Computing, 1996, vol. 25, no. 6, pp. 1305–1317. doi: 10.1137/S0097539793251219
7. Bodlaender H. L. Treewidth: Algorithmic techniques and results. In: Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS’97). Berlin, Heidelberg: Springer, 1997, pp. 19–36. doi: 10.1007/BFb0029946
8. Bodlaender H. L. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 1998, vol. 209, no. 1–2, pp. 1–45. doi: 10.1016/S0304-3975(97)00228-4
9. Bodlaender H. L. Treewidth: Characterizations, applications, and computations. In: F.V. Fomin (ed.), Graph-Theoretic Concepts in Computer Science (WG 2006). 2006, Lecture Notes in Computer Science; vol 4271, pp. 1–14. doi: 10.1007/11917496_1
10. Chekuri C., Ene A., Korula N. (2009) Unsplittable flow in paths and trees and column-restricted packing integer programs. In: Dinur I. et al. (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX 2009, RANDOM 2009). 2009. Lecture Notes in Computer Science; vol. 5687, pp .42–55. doi: 10.1007/978-3-642-03685-9_4
11. Cornuejols G., Nemhauser G. L., Wolsey L. A. The uncapacitated facility location problem. Discrete location theory. Mirchandani P. B. and Francis R. L. (eds). N Y: Wiley, 1990, pp. 119–171.
12. Cygan M., Fomin F.V., Kowalik L., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M., Saurabh S. Parameterized algorithms. Cham: Springer, 2015, 613 p. doi: 10.1007/978-3-319-21275-3
13. Dinitz Y., Garg N., Goemans M.X. On the single-source unsplittable flow problem. Proc. 39th Annual Symposium on Foundations of Computer Science. Palo Alto, CA, USA, 1998, pp. 290–299. doi: 10.1109/SFCS.1998.743461
14. Gimadi E. Kh., Kurochkina A., Tsidulko O. On exact solvability of the restricted capacitated facility location problem. CEUR-WS, 2017, vol. 1987, pp. 209–216.
15. Granot D., Skorin-Kapov D. On some optimization problems on k-trees and partial k-trees. Discrete Appl. Math., 1994, vol. 48, no. 2, pp. 129–145. doi: 10.1016/0166-218X(92)00122-3
16. Guruswami V., Khanna S., Rajaraman R., Shepherd B., Yannakakis M. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Computer and System Sciences, 2003, vol. 67, no. 3, pp. 473–496. doi: 10.1016/S0022-0000(03)00066-7
17. 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 .
18. Kleinberg J.M. Approximation algorithms for disjoint paths problems. Ph.D. dissertation, M.I.T., 1996, 188 p.
19. Koivisto M., Manila H., Perola M., Varilo T., Hennah W., Ekelund J., Lukk M., Peltonen L., Ukkonen E. An MDL method for finding haplotype blocks and for estimating the strength of block boundaries. In: Pacific Symposium on Biocomputing, 2003, pp. 502–513. doi: 10.1142/9789812776303_0047
20. Laporte G., Nickel S., Saldanha da Gama F. Location science. Switzerland: Springer Intern. Publ., 2015, 650 p.
21. Lazic N., Givoni I. E., Frey B. J., Aarabi P. FLoSS: Facility location for subspace segmentation. IEEE 12th Intern. Conf. on Computer Vision, Kyoto, 2009, pp. 825–832. doi: 10.1109/ICCV.2009.5459302
22. Robertson N., Seymour P.D. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 1986, vol. 7, no. 3, pp. 309–322. doi: 10.1016/0196-6774(86)90023-4
23. Shah R., Farach-Colton M. Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. Proc. of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 2002, pp. 108–115.
24. Turner L., Gross D. P., Hamacher H. W., Krumke S. O. Static and dynamic source locations in undirected networks. TOP., 2015, vol. 23, pp. 619–646. doi: 10.1007/s11750-015-0395-7
25. Voznyuk I.P. The location problem on networks with bounded communication capacities. Diskretn. Anal. Issled. Oper., Ser. 2, 1999, vol. 6, no. 1, pp. 3–11 (in Russian).
26. Voznyuk I.P. The plant location problem on a two-tree with bounded communication capacities. Diskretn. Anal. Issled. Oper., Ser. 2, 2000, vol. 7, no. 1, pp. 3–8 (in Russian).
27. Wilber R. The concave least-weight subsequence problem revisited. J. Algorithms, 1988, vol. 9. pp. 418–425. doi 10.1016/0196-6774(88)90032-6 .
Cite this article as: E.Kh. Gimadi, O.Yu. Tsidulko. On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 2, pp. 108–124; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 313, Suppl. 1, pp. S58–S72.
