Geodesic
Exact algorithm for solving discrete Weber problem for a~cycle
Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 96-102.

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

A polynomial algorithm solving discrete Weber problem for cycle and for finite set of location positions is presented. The algorithm is based on the dynamic programming idea. The comparison of action times of the given algorithm and of an integer linear programming model, which was realized in IBM ILOG CPLEX, is carried out.
Keywords: Weber problem, cycle, dynamic programming, exact algorithm. 
@article{PDM_2013_4_a9,
     author = {R. E. Shangin},
     title = {Exact algorithm for solving discrete {Weber} problem for a~cycle},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {96--102},
     publisher = {mathdoc},
     number = {4},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_4_a9/}
}
TY  - JOUR
AU  - R. E. Shangin
TI  - Exact algorithm for solving discrete Weber problem for a~cycle
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 96
EP  - 102
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_4_a9/
LA  - ru
ID  - PDM_2013_4_a9
ER  - 
%0 Journal Article
%A R. E. Shangin
%T Exact algorithm for solving discrete Weber problem for a~cycle
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 96-102
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_4_a9/
%G ru
%F PDM_2013_4_a9
R. E. Shangin. Exact algorithm for solving discrete Weber problem for a~cycle. Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 96-102. http://geodesic.mathdoc.fr/item/PDM_2013_4_a9/

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

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

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

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

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

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

[7] Shangin R. E., “Razrabotka i analiz algoritmov dlya zadachi Vebera”, Problemy optimizatsii i ekonomicheskie prilozheniya, Omsk, 2012, 121–122

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

[9] Zabudsky G. G., Filimonov D. V., “An algorithm for minimax location problem on tree with maximal distances”, Proc. Second Intern. Workshop “Discrete Optimization Methods in Production and Logistics” (DOM2004), Omsk, 2004, 81–85

[10] Zabudskii G. G., Filimonov D. V., “O minimaksnoi i minisummnoi zadachakh razmescheniya na setyakh”, Trudy XII Baikalskoi Mezhdunar. konf. “Metody optimizatsii i ikh prilozheniya”, Omsk, 2001, 150–155

[11] Filimonov D. V., “Reshenie diskretnoi minimaksnoi zadachi razmescheniya na drevovidnoi seti”, Materialy ezhegodnogo nauchnogo seminara aspirantov, Omsk, 2003, 58–61