Geodesic
An optimal algorithm for an outerplanar facility location problem with improved time complexity
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 74-81
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider a network facility location problem with unbounded production levels. This problem is NP-hard in the general case and is known to have an optimal solution with quadratic complexity on a tree network. We study the case of a network representable by an outerplanar graph, i.e., by a graph whose vertices belong to one (outer) face. This problem is known to have an optimal algorithm with time complexity $O(nm^3)$, where $n$ is the number of vertices and $m$ is the number of possible facility locations. Using some properties of outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally connected service domains, we obtain recurrence relations for the construction of an optimal algorithm with time complexity that is smaller by a factor of $\sqrt{m}$ than the time complexity of the earlier algorithm.
Keywords: facility location problem, network, outerplanar graph, time complexity, connectedness.
Mots-clés : optimal algorithm 
@article{TIMM_2017_23_3_a5,
     author = {E. Kh. Gimadi},
     title = {An optimal algorithm for an outerplanar facility location problem with improved time complexity},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {74--81},
     year = {2017},
     volume = {23},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a5/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
TI  - An optimal algorithm for an outerplanar facility location problem with improved time complexity
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2017
SP  - 74
EP  - 81
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a5/
LA  - ru
ID  - TIMM_2017_23_3_a5
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%T An optimal algorithm for an outerplanar facility location problem with improved time complexity
%J Trudy Instituta matematiki i mehaniki
%D 2017
%P 74-81
%V 23
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a5/
%G ru
%F TIMM_2017_23_3_a5
E. Kh. Gimadi. An optimal algorithm for an outerplanar facility location problem with improved time complexity. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 74-81. http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a5/

[1] Discrete location theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, eds. eds. P.B. Mirchandani, R.L. Francis, Wiley and Sons Inc., N.Y.; Chichester; Brisbane; Toronto; Singapour, 1990, 576 pp. | MR | Zbl

[2] Trubin V.A., “Effektivnyi algoritm resheniya zadachi razmescheniya na seti v forme dereva”, Dokl. AN SSSR, 231:3 (1976), 547–550 | MR | Zbl

[3] Kolen A., “Solving covering problems and the uncapacitated plant location on the trees”, Eur. J. Oper. Res., 12:3 (1983), 266–278 | DOI | MR | Zbl

[4] Gimadi E.Kh., “Effektivnyi algoritm razmescheniya s oblastyami obsluzhivaniya, svyaznymi otnositelno atsiklicheskoi seti”, Upravlyaemye sistemy, sb. st., v. 23, IM SO RAN, Novosibirsk, 1983, 12–23

[5] Billionet A., Costa M.-C., “Solving the uncapacitated plant location problem on trees”, Discrete Appl. Math., 49:1–3 (1994), 51–59 | DOI | MR

[6] Ageev A.A., “Polinomialnyi algoritm resheniya zadachi razmescheniya na posledovatelno-parallelnoi seti”, Upravlyaemye sistemy, cb. st., v. 30, IM SO RAN, Novosibirsk, 1990, 3–16

[7] Gimadi E.Kh., “Zadacha razmescheniya na seti s tsentralno-svyaznymi oblastyami obsluzhivaniya”, Upravlyaemye sistemy, sb. st., v. 25, IM SO RAN, Novosibirsk, 1984, 38–47

[8] Valdes J., Tarjan R., Lawler E., “The recognition of series parallel digraphs”, SIAM J. Comput., 11:2 (1982), 298–313 | DOI | MR | Zbl

[9] Ageev A.A., “Grafy, matritsy i prosteishaya zadacha razmescheniya”, Upravlyaemye sistemy, sb. st., v. 7, IM SO RAN, Novosibirsk, 1989, 3–11

[10] Hassin R., Tamir A., “Efficient algorithm for optimization and selection on series-parallel graphs”, SIAM J. Algebraic Discrete Methods, 7:3 (1986), 379–389 | DOI | MR | Zbl