Geodesic
Polynomial algorithms for solving the quadratic bottleneck assignment problem on networks
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 4, pp. 49-65.

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

The quadratic bottleneck assignment problem in terms of graphs is considered. The goal is to find permutation of the graph vertices on the network nodes that minimizes the cost between adjacent vertices. We provide polynomial algorithms for solving the problem on special networks. Ill. 7, bibliogr. 13.
Keywords: quadratic bottleneck assignment problem, location problem, graph.
Mots-clés : polynomial algorithm 
@article{DA_2011_18_4_a2,
     author = {G. G. Zabudsky and A. Yu. Lagzdin},
     title = {Polynomial algorithms for solving the quadratic bottleneck assignment problem on networks},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {49--65},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_4_a2/}
}
TY  - JOUR
AU  - G. G. Zabudsky
AU  - A. Yu. Lagzdin
TI  - Polynomial algorithms for solving the quadratic bottleneck assignment problem on networks
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 49
EP  - 65
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_4_a2/
LA  - ru
ID  - DA_2011_18_4_a2
ER  - 
%0 Journal Article
%A G. G. Zabudsky
%A A. Yu. Lagzdin
%T Polynomial algorithms for solving the quadratic bottleneck assignment problem on networks
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 49-65
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_4_a2/
%G ru
%F DA_2011_18_4_a2
G. G. Zabudsky; A. Yu. Lagzdin. Polynomial algorithms for solving the quadratic bottleneck assignment problem on networks. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 4, pp. 49-65. http://geodesic.mathdoc.fr/item/DA_2011_18_4_a2/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[2] Demidenko V. M., “Obobschenie uslovii silnoi razreshimosti kvadratichnoi zadachi o naznacheniyakh s matritsami anti-Monzha i Teplitsa”, Dokl. NAN Belarusi, 47:2 (2003), 15–18 | MR | Zbl

[3] Zabudskii G. G., “O nekotorykh zadachakh razmescheniya na grafakh”, Metody optimizatsii i ikh prilozheniya, Tr. XI Baikalskoi mezhdunar. shkoly-seminara, ISE im. L. A. Melenteva SO RAN, Irkutsk, 1998, 135–138

[4] Zabudskii G. G., Lagzdin A. Yu., “Algoritm resheniya kvadratichnoi zadachi o naznacheniyakh s minimaksnym kriteriem na dereve”, Dinamika sistem, mekhanizmov i mashin, Materialy VII Mezhdunar. nauchno-tekhn. konf., v. 3, OmGTU, Omsk, 2009, 23–27

[5] Iordanskii M. A., “O minimaksnykh numeratsiyakh vershin grafa”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, Mezhvuz. sb., GGU im. Lobachevskogo, Gorkii, 1986, 60–73 | MR

[6] Metelskii N. N., “Metody lokalnoi optimizatsii dlya zadachi razmescheniya dvudolnykh grafov”, Zhurn. vychisl. matematiki i mat. fiziki, 24:9 (1984), 1428–1432 | MR | Zbl

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

[8] Arkin E., Hassin R., Sviridenko M., “Approximating the maximum quadratic assignment problem”, Inf. Process. Lett., 77 (2001), 13–16 | DOI | MR | Zbl

[9] Burkard R. E., Dell'Amico M., Mortello S., Assignment problems, SIAM, Philadelphia, 2009, 402 pp. | MR | Zbl

[10] Burkard R. E., Fincke U., “On random quadratic bottleneck assignment problems”, Math. Programming, 23:1 (1982), 227–232 | DOI | MR | Zbl

[11] Farahani R. Z., Hekmatfar M., Facility location: concepts, models, algorithms and case studies, Physica-Verl., Heidelberg, 2009, 543 pp.

[12] Haralambides J., Makedon F., “Approximation algorithms for the bandwidth minimization problem for a large class of trees”, Theory Comput. Syst., 30:1 (1997), 67–90 | MR | Zbl

[13] Steinberg L., “The backboard wiring problem: a placement algorythm”, SIAM, 3:1 (1961), 37–50 | DOI | MR | Zbl