Geodesic
Effective algorithm for solving a~two-level facility location problem on a~tree-like network
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 9-22.

Voir la notice de l'article provenant de la source Math-Net.Ru

A two-level facility location problem on a tree-like network is considered. The transportation cost between each pair of sites is defined as the length of the corresponding path in the network. An exact algorithm for solving the problem with time-complexity equals to $O(nm^3)$ is constructed, where $n$ is the number of consumers and $m$ is the maximum number of facilities at both levels. Il. 3, bibliogr. 7.
Keywords: $2$-level facility location problem, tree-like network.
Mots-clés : polynomial algorithm 
@article{DA_2012_19_6_a1,
     author = {E. Kh. Gimadi and A. A. Kurochkin},
     title = {Effective algorithm for solving a~two-level facility location problem on a~tree-like network},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {9--22},
     publisher = {mathdoc},
     volume = {19},
     number = {6},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_6_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - A. A. Kurochkin
TI  - Effective algorithm for solving a~two-level facility location problem on a~tree-like network
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 9
EP  - 22
VL  - 19
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_6_a1/
LA  - ru
ID  - DA_2012_19_6_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A A. A. Kurochkin
%T Effective algorithm for solving a~two-level facility location problem on a~tree-like network
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 9-22
%V 19
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_6_a1/
%G ru
%F DA_2012_19_6_a1
E. Kh. Gimadi; A. A. Kurochkin. Effective algorithm for solving a~two-level facility location problem on a~tree-like network. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 9-22. http://geodesic.mathdoc.fr/item/DA_2012_19_6_a1/

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

[2] Gimadi E. Kh., “Effektivnye algoritmy dlya resheniya mnogoetapnoi zadachi razmescheniya na tsepi”, Diskret. analiz i issled. operatsii, 2:4 (1995), 13–31 | MR | Zbl

[3] Ageev A., Ye Yi., Zhang J., “Improved combinatorial approximation algorithms for the $k$-level facility location problem”, SIAM J. Discrete Math., 18:1 (2004), 207–217 | DOI | MR | Zbl

[4] Gimadi E. Kh., “Exact algorithm for some multi-level location problems on a chain and a tree”, Oper. Res. Proc. SOR' 96 (Braunschweig, Germany, September 3–6, 1996), Springer-Verl., Berlin, 1997, 72–77 | DOI | MR | Zbl

[5] P. B. Mirchandani, R. L. Francis (eds.), Discrete location theory, Wiley-Intersci. Ser. Discrete Math. Optimization, Wiley Sons Inc., New York–Chichester–Brisbane–Toronto–Singapour, 1990, 555 pp. | MR | Zbl

[6] Zhang J., “Approximating the two-level facility location problem via a quasi-greedy approach”, Proc. 15th ACM-SIAM Symp. Discrete Algorithms SODA (New Orleans, Louisiana, USA, January 11–14, 2004), SIAM, Philadelphia, 2004, 808–817 | MR

[7] Bumb A. F., Kern W., “A simple dual ascent algorithm for the multilevel facility location problem”, 4th Int. Workshop Approximation Algorithms Comb. Optimization APPROX 2001 (Berkeley, CA, USA, August 18–20, 2001), Lect. Notes Comput. Sci., 2129, Springer-Verl., London, 2001, 55–62 | DOI | MR | Zbl