Geodesic
An exact algorithm for solving the discrete Weber problem for a~$k$-tree
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 64-75.

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

We consider the discrete Weber problem. A consistent deterministic algorithm for finding an exact solution to the problem for a $k$-tree and a finite set of placement positions is suggested. The algorithm is based on the idea of dynamic programming with a decomposition tree. A numerical experiment was performed to examine the effectiveness of the proposed algorithm in comparison with IBM ILOG CPLEX. Ill. 2, bibliogr. 23.
Keywords: Weber problem, $k$-tree, dynamic programming, decomposition tree, exact algorithm. 
@article{DA_2014_21_3_a6,
     author = {A. V. Panyukov and R. E. Shangin},
     title = {An exact algorithm for solving the discrete {Weber} problem for a~$k$-tree},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {64--75},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_3_a6/}
}
TY  - JOUR
AU  - A. V. Panyukov
AU  - R. E. Shangin
TI  - An exact algorithm for solving the discrete Weber problem for a~$k$-tree
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 64
EP  - 75
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_3_a6/
LA  - ru
ID  - DA_2014_21_3_a6
ER  - 
%0 Journal Article
%A A. V. Panyukov
%A R. E. Shangin
%T An exact algorithm for solving the discrete Weber problem for a~$k$-tree
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 64-75
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_3_a6/
%G ru
%F DA_2014_21_3_a6
A. V. Panyukov; R. E. Shangin. An exact algorithm for solving the discrete Weber problem for a~$k$-tree. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 64-75. http://geodesic.mathdoc.fr/item/DA_2014_21_3_a6/

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

[2] Bykova V. V., “FTP-algoritmy na grafakh ogranichennoi drevovidnoi shiriny”, Prikl. diskret. matematika, 2012, no. 2, 65–78

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

[4] Zabudskii G. G., Lagzdin A. Yu., “Dinamicheskoe programmirovanie dlya resheniya kvadratichnoi zadachi o naznacheniyakh na dereve”, Avtomatika i telemekhanika, 2012, no. 2, 141–155

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

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

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

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

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

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

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

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

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

[14] Arnborg S., “Efficient algorithms for combinatorial problems with bounded decomposability – a survey”, BIT Numerical Math., 25:1 (1985), 1–23 | DOI | MR

[15] Arnborg S., Proskurowski A., “Linear time algorithms for NP-hard problems restricted to partial $k$-trees”, Discrete Appl. Math., 23 (1989), 11–24 | DOI | MR | Zbl

[16] Bodlaender H. L., “Treewidth: algorithmic techniques and results”, Lect. Notes Comput. Sci., 1295, 1997, 19–36 | DOI | MR | Zbl

[17] Ibarra L., “The clique-separator graph for chordal graphs”, Discrete Appl. Math., 157:8 (2009), 1737–1749 | DOI | MR | Zbl

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

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

[20] Robertson N., Seymour P. D., “Graph minors. II. Algorithmic aspects of treewidth”, J. Algorithms, 7 (1986), 309–322 | DOI | MR | Zbl

[21] Rose D. J., “Triangulated graphs and the elimination process”, J. Math. Anal. Appl., 32 (1970), 597–609 | DOI | MR | Zbl

[22] Rose D. J., “On simple characterizations of $k$-trees”, Discrete Math., 7 (1973), 317–322 | DOI | MR

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