Geodesic
A deterministic algorithm for solving the Weber problem for an $n$-sequentially connected chain
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 5, pp. 84-96.

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

The class of $n$-sequentially connected chains is introduced. Here is set an algorithm based on dynamic programming which reasonably solves the Weber problem for an $n$-sequentially connected chain and a finite set of location positions. The analysis of the proposed algorithm is given. On a set of problem cases which was randomly generated, the comparison of action period of the given algorithm and a model of integer linear programming was carried out in IBM ILOG CPLEX. Ill. 3, tab. 1, bibliogr. 16.
Keywords: Weber problem, $n$-sequentially connected chain, dynamic programming, exact algorithm. 
@article{DA_2013_20_5_a6,
     author = {R. E. Shangin},
     title = {A deterministic algorithm for solving the {Weber} problem for an $n$-sequentially connected chain},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {84--96},
     publisher = {mathdoc},
     volume = {20},
     number = {5},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_5_a6/}
}
TY  - JOUR
AU  - R. E. Shangin
TI  - A deterministic algorithm for solving the Weber problem for an $n$-sequentially connected chain
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 84
EP  - 96
VL  - 20
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_5_a6/
LA  - ru
ID  - DA_2013_20_5_a6
ER  - 
%0 Journal Article
%A R. E. Shangin
%T A deterministic algorithm for solving the Weber problem for an $n$-sequentially connected chain
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 84-96
%V 20
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_5_a6/
%G ru
%F DA_2013_20_5_a6
R. E. Shangin. A deterministic algorithm for solving the Weber problem for an $n$-sequentially connected chain. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 5, pp. 84-96. http://geodesic.mathdoc.fr/item/DA_2013_20_5_a6/

[1] Bykova V. V., “Vychislitelnye aspekty drevovidnoi shiriny grafa”, Prikl. diskret. matematika, 2011, no. 3, 65–79

[2] Zabudskii G. G., Lagzdin A. Yu., “Polinomialnye algoritmy resheniya minimaksnoi kvadratichnoi zadachi o naznacheniyakh na setyakh”, Diskret. analiz i issled. operatsii, 18:4 (2011), 49-65 | MR | Zbl

[3] Zabudskii G. G., Filimonov D. V., “O minimakskoi i minisummnoi zadachakh razmescheniya na setyakh”, Tr. XII Baikalskoi mezhdunar. konf. “Metody optimizatsii i ikh prilozheniya” (Irkutsk, 24 iyunya – 1 iyulya 2001 g.), Izd-vo IGU, Irkutsk, 2001, 150–155

[4] Panyukov A. V., Modeli i metody resheniya zadach postroeniya i identifikatsii geometricheskogo razmescheniya, Dis. $\dots$ d-ra fiz.-mat. nauk, Yuzhnouralskii un-t, Chelyabinsk, 1999, 260 pp.

[5] Panyukov A. V., Peltsverger B. F., “Optimalnoe razmeschenie dereva v konechnom mnozhestve”, Zhurn. vychisl. matematiki i mat. fiziki, 28:4 (1988), 618–620 | MR | Zbl

[6] Panyukov A. V., Peltsverger B. F., Shafir A. Yu., “Optimalnoe razmeschenie tochek vetvleniya transportnoi seti na tsifrovoi modeli mestnosti”, Avtomatika i telemekhanika, 1990, no. 9, 153–162 | MR | Zbl

[7] Sergeev S. I., “Kvadratichnaya zadacha o naznacheniyakh. I”, Avtomatika i telemekhanika, 1999, no. 8, 127–147 | MR | Zbl

[8] Trubin V. A., “Effektivnyi algoritm dlya zadachi Vebera s pryamougolnoi metrikoi”, Kibernetika, 1978, no. 6, 67–70 | MR | Zbl

[9] Filimonov D. V., “Reshenie diskretnoi minimaksnoi zadachi razmescheniya na drevovidnoi seti”, Mat. ezhegod. nauch. seminara aspirantov i studentov-vypusknikov, Izd-vo Omsk. gos. un-ta, Omsk, 2003, 58–61

[10] Shangin R. E., “Issledovanie effektivnosti priblizhennykh algoritmov resheniya odnogo chastnogo sluchaya zadachi Vebera”, Ekonomika, statistika i informatika. Vestn. UMO, 2012, no. 1, 163–169

[11] Shangin R. E., “O nekotorykh svoistvakh $n$-posledovatelnosvyaznoi tsepi”, Vestn. YuUrGU. Ser. Vychisl. matematika i informatika, 2:1 (2013), 106–113

[12] Shangin R. E., “Kvazipolinomialnyi algoritm dlya resheniya zadachi Vebera dlya $n$-posledovatelnosvyaznogo tsikla”, Obozrenie prikl. i prom. matematiki, 19:4 (2012), 122–124

[13] Shangin R. E., “Razrabotka i analiz algoritmov dlya zadachi Vebera”, Tez. dokl. mezhdunar. konf. “Problemy optimizatsii i ekonomicheskie prilozheniya” (Omsk, 2–6 iyulya 2012 g.), Izd-vo Omsk. gos. un-ta, Omsk, 2012, 121

[14] McKee T. A., “On the chordality of a graph”, J. Graph Theory, 17 (1993), 221–232 | DOI | MR | Zbl

[15] Panyukov A. V., Pelzwerger B. V., “Polynomial algorithms to finite Weber problem for a tree network”, J. Comput. Appl. Math., 35 (1991), 291–296 | DOI | MR | Zbl

[16] Zabudsky G. G., Filimonov D. V., “An algorithm for minimax location problem on a tree with maximal distances”, Proc. 2nd Int. Workshop Discrete Optimization Methods in Production and Logistics (DOM2004), ISU Press, Omsk–Irkutsk, 2004, 81–85