УДК 519.8
MSC: 90-02, 90B80
DOI: 10.21538/0134-4889-2020-26-2-108-124
Работа выполнена при поддержке РФФИ (проект 18-31-00470) и частичной поддержке Математического Центра в Академгородке (соглашение с Министерством науки и высшего образования Российской Федерации 075-15-2019-1675).
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2021, Vol. 313, Suppl. 1, pp. S58–S72. (Abstract)
В работе исследуется задача размещения в сетях с ограниченными пропускными способностями коммуникаций, в которой требуется разместить предприятия в вершинах заданной сети так, чтобы с минимальными затратами единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Рассматриваются постановки задачи с делимыми спросами, где спрос клиента может быть удовлетворен несколькими предприятиями совместно, и неделимыми спросами, тогда спрос клиента должен быть целиком удовлетворен одним предприятием. В работе показано, что задача с неделимыми спросами NP-трудна, даже если заданная сеть является простым путем, и NP-трудна в сильном смысле, если сеть — дерево. Задача с делимыми спросами слабо NP-трудна на деревьях. Для этой задачи в работе предложен псевдополиномиальный алгоритм решения на графах с древесной шириной, ограниченной константой, а также представлен линейный алгоритм для случая, когда граф сети является простым путем.
Ключевые слова: задача размещения, пропускные способности, делимый спрос, неделимый спрос, NP-трудная задача, древесная ширина, псевдополиномиальный алгоритм, полиномиальный алгоритм
СПИСОК ЛИТЕРАТУРЫ
1. Adamaszek A., Chalermsook P., Ene A., Wiese A. Submodular unsplittable flow on trees // Math. Program. 2018. Vol. 172. P. 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. P. 237–245.
3. Andreev K., Garrod C., Golovin D., Maggs B., Meyerson A. Simultaneous source location // ACM Trans. Algorithms. 2010. Vol. 6, no. 1. P. 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. P. 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. Lecture Notes in Computer Science; vol. 1776. P. 88–94. doi: 10.1007/10719839_9
6. Bodlaender H. L. A linear time algorithm for finding tree-decompositions of small treewidth // SIAM J. Computing. 1996. Vol. 25, no. 6. P. 1305–1317. doi: 10.1137/S0097539793251219
7. Bodlaender H. L. Treewidth: Algorithmic techniques and results // Proc. of the 22nd Internat. Symposium on Mathematical Foundations of Computer Science (MFCS’97). Berlin, Heidelberg: Springer, 1997. P. 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, iss. 1–2. P. 1–45. doi: 10.1016/S0304-3975(97)00228-4
9. Bodlaender H. L. Treewidth: Characterizations, applications, and computations // Graph-Theoretic Concepts in Computer Science (WG 2006) / ed. F.V. Fomin. Lecture Notes in Computer Science; vol. 4271. 2006. P. 1–14. doi: 10.1007/11917496_1
10. Chekuri C., Ene A., Korula N. Unsplittable flow in paths and trees and column-restricted packing integer programs // Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX 2009, RANDOM 2009) / eds. I. Dinur et al. 2009. Lecture Notes in Computer Science; vol. 5687. P. 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 / eds. P. B. Mirchandani and R. L. Francis. N Y: Wiley, 1990. P. 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. P.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. P. 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. P. 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 System Sci. 2003. Vol. 67, no. 3, P. 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. P. 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 // Pacific Symposium on Biocomputing, 2003. P. 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. P. 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, P. 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. P. 108–115.
24. Turner L., Gross D. P., Hamacher H. W., Krumke S. O. Static and dynamic source locations in undirected networks // TOP. Vol. 23. 2015. P. 619–646. doi: 10.1007/s11750-015-0395-7 .
25. Вознюк И. П. Задача размещения на сети с ограниченными пропускными способностями коммуникаций // Дискретный анализ и исследование операций. Сер. 2. 1999. Т. 6, вып. 1. С. 3–11.
26. Вознюк И. П. Задача размещения пунктов производства на два-дереве с ограниченными пропускными способностями коммуникаций // Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, вып. 1. С. 3–8.
27. Wilber R. The concave least-weight subsequence problem revisited // J. Algorithms. 1988. Vol. 9. P. 418–425. doi 10.1016/0196-6774(88)90032-6
Поступила 24.03.2020
После доработки 14.05.2020
Принята к публикации 18.05.2020
Гимади Эдуард Хайрутдинович
д.-р. физ.-мат. наук, профессор
главный науч. сотрудник
Институт математики им С.Л.Соболева СО РАН;
Новосибирский государственный университет
г. Новосибирск
e-mail: gimadi@math.nsc.ru
Цидулко Оксана Юрьевна
канд. физ.-мат. наук
науч. сотрудник
Институт математики им С.Л.Соболева СО РАН;
Новосибирский государственный университет
г. Новосибирск
e-mail: tsidulko@math.nsc.ru
Ссылка на статью: Э.Х. Гимади, О.Ю. Цидулко. О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций // Тр. Ин-та математики и механики УрО РАН. 2020. Т.26, № 2. С. 108-124
English
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
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
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.
[References -> on the "English" button bottom right]
