Geodesic
On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 2, pp. 108-124 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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 at minimum cost the demands of customers located at the vertices of the graph. We consider two statements of the problem: the multiple allocation RFLP, where the demand of a customer can be satisfied jointly by several facilities, and the single allocation RFLP, where the demand of a customer 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-time algorithm for the case where the network graph has constant treewidth and a linear-time algorithm for the case where the network is a simple path.
Keywords: facility location problem, capacities, multiple allocation, single allocation, NP-hard problem, treewidth
Mots-clés : pseudopolynomial-time algorithm, polynomial-time algorithm. 
@article{TIMM_2020_26_2_a8,
     author = {E. Kh. Gimadi and O. Yu. Tsidulko},
     title = {On {Some} {Efficiently} {Solvable} {Classes} of the {Network} {Facility} {Location} {Problem} with {Constraints} on the {Capacities} of {Communication} {Lines}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {108--124},
     year = {2020},
     volume = {26},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - O. Yu. Tsidulko
TI  - On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2020
SP  - 108
EP  - 124
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/
LA  - ru
ID  - TIMM_2020_26_2_a8
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A O. Yu. Tsidulko
%T On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
%J Trudy Instituta matematiki i mehaniki
%D 2020
%P 108-124
%V 26
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/
%G ru
%F TIMM_2020_26_2_a8
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 mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 2, pp. 108-124. http://geodesic.mathdoc.fr/item/TIMM_2020_26_2_a8/

[1] Adamaszek A., Chalermsook P., Ene A., Wiese A., “Submodular unsplittable flow on trees”, Math. Program., 172 (2018), 565–589 | DOI | MR | Zbl

[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, Carnegie Mellon University, Pittsburgh, 1992, 237–245

[3] Andreev K., Garrod C., Golovin D., Maggs B., Meyerson A., “Simultaneous source location”, ACM Trans. Algorithms, 6:1 (2010), 16:1–16:17 | DOI | MR

[4] Arata K., Iwata S., Makino K., Fujishige S., “Locating sources to meet flow demands in undirected networks”, J. Algorithms, 42 (2002), 54–68 | DOI | MR | Zbl

[5] Bender M. A., Farach-Colton M., “The LCA problem revisited”, 4th Latin American Symposium on Theoretical Informatics (LATIN), Lecture Notes in Computer Science, 1776, 2000, 88–94 | DOI | MR | Zbl

[6] Bodlaender H. L., “A linear time algorithm for finding tree-decompositions of small treewidth”, SIAM J. Computing, 25:6 (1996), 1305–1317 | DOI | MR | Zbl

[7] Bodlaender H. L., “Treewidth: Algorithmic techniques and results”, Proc. of the 22nd Internat. Symposium on Mathematical Foundations of Computer Science (MFCS'97), Springer, Berlin, Heidelberg, 1997, 19–36 | DOI | MR | Zbl

[8] Bodlaender H. L., “A partial $k$-arboretum of graphs with bounded treewidth”, Theoretical Computer Science, 209: 1–2 (1998), 1–45 | DOI | MR | Zbl

[9] Bodlaender H. L., “Treewidth: Characterizations, applications, and computations”, Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science, 4271, ed. F.V. Fomin, 2006, 1–14 | DOI | MR | Zbl

[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), Lecture Notes in Computer Science, 5687, eds. I. Dinur et al., 2009, 42–55 | DOI | MR | Zbl

[11] Cornuéjols G., Nemhauser G. L., Wolsey L. A., “The uncapacitated facility location problem”, Discrete location theory, eds. P. B. Mirchandani and R. L. Francis, Wiley, N Y, 1990, 119–171 | MR

[12] Cygan M., Fomin F.V., Kowalik L., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M., Saurabh S., Parameterized algorithms, Springer, Cham, 2015, 613 pp. | DOI | MR | Zbl

[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), 290–299 | DOI | MR

[14] Gimadi E. Kh., Kurochkina A., Tsidulko O., “On exact solvability of the restricted capacitated facility location problem”, CEUR-WS, 1987 (2017), 209–216

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

[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., 67:3 (2003), 473–496 | DOI | MR | Zbl

[17] 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

[18] Kleinberg J.M., Approximation algorithms for disjoint paths problems , Ph.D. dissertation, M.I.T., 1996, 188 pp.

[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, 502–513 | DOI

[20] Laporte G., Nickel S., Saldanha da Gama F., Location science, Springer Intern. Publ., Switzerland, 2015, 650 pp. | MR | Zbl

[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), 825–832 | DOI

[22] Robertson N., Seymour P.D., “Graph minors. II. Algorithmic aspects of tree-width”, J. Algorithms, 7:3 (1986), 309–322 | DOI | MR | Zbl

[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, 108–115 | Zbl

[24] Turner L., Gross D. P., Hamacher H. W., Krumke S. O., “Static and dynamic source locations in undirected networks”, TOP, 23 (2015), 619–646 | DOI | MR | Zbl

[25] 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

[26] 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

[27] Wilber R., “The concave least-weight subsequence problem revisited ”, J. Algorithms, 9 (1988), 418–425 | DOI | MR | Zbl