Geodesic
Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability
Diskretnaya Matematika, Tome 19 (2007) no. 1, pp. 105-132 
V. M. Demidenko. Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability. Diskretnaya Matematika, Tome 19 (2007) no. 1, pp. 105-132. http://geodesic.mathdoc.fr/item/DM_2007_19_1_a12/
@article{DM_2007_19_1_a12,
     author = {V. M. Demidenko},
     title = {Quadratic assignment problems with additively monotone matrices and incomplete {anti-Monge} matrices: conditions for effective solvability},
     journal = {Diskretnaya Matematika},
     pages = {105--132},
     year = {2007},
     volume = {19},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_1_a12/}
}
TY  - JOUR
AU  - V. M. Demidenko
TI  - Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 105
EP  - 132
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_1_a12/
LA  - ru
ID  - DM_2007_19_1_a12
ER  - 
%0 Journal Article
%A V. M. Demidenko
%T Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability
%J Diskretnaya Matematika
%D 2007
%P 105-132
%V 19
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2007_19_1_a12/
%G ru
%F DM_2007_19_1_a12

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

For classes of additively monotone matrices and incomplete anti-Monge matrices, we describe conditions which guarantee the attainment of the optimum of the functional of the quadratic assignment problem at a given permutation. The suggested conditions generalise and unify all special cases of the quadratic assignment problems with anti-Monge and Toeplitz matrices, including the well-known theorem on a permutation of three systems proved by G. H. Hardy, J. E. Littlewood, and G. Pólya in 1926, and all known extensions of this theorem.

[1] Lawler L. E., “The quadratic assignment problem”, Manage. Sci., 9 (1963), 586–599 | DOI | MR | Zbl

[2] Pardalos P., Rendl F., Wolkowicz H., “The quadratic assignment problem: A survey and recent developments”, DIMACS, Ser. Discrete Math. Theor. Comput. Sci., 16 (1994), 1–42 | MR | Zbl

[3] Burkard R. E., Çela E., Demidenko V. M., Metelski N. N., Woeginger G. J., Perspectives of easy and hard cases of the quadratic assignment problem, Report No104, Techn. Univ. Graz, 1997

[4] Burkard R. E., Klinz B., Rudolf R., “Perspectives of Monge properties in optimization”, Discrete Appl. Math., 70 (1996), 95–161 | DOI | MR | Zbl

[5] Koopmans T. C., Beckmann M. J., “Assignment problems and the location of economic activities”, Econometrica, 25 (1957), 53–76 | DOI | MR | Zbl

[6] Burkard R. E., Çela E., Rote R., Woeginger G. J., “The quadratic assignment problem with an anti-Monge and a Toeplitz matrix: easy and hard cases”, Math. Program., 82 (1998), 125–158 | MR | Zbl

[7] Çela E., Woeginger G. J., A note on the maximum of a certain bilinear form, Report No8, Techn. Univ. Graz, 1994

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

[9] Khardi G. G., Littlvud Dzh. E., Polia G., Neravenstva, GIIL, Moskva, 1948

[10] Hardy G. H., Littlewood J. E., Pólya G., “The maximum of a certain bilinear form”, Proc. London Math. Soc., 25 (1926), 265–282 | DOI | Zbl

[11] Timofeev B. B., Litvinov V. A., “Ob ekstremalnykh znacheniyakh kvadratichnoi formy”, Kibernetika, 1969, no. 4, 56–61 | Zbl

[12] Vickson R. G., Lu X., “Optimal product and server locations in one-dimensional storage racks”, European J. Oper. Res., 105 (1998), 18–28 | DOI | Zbl

[13] Burkov V. N., Rubinshtein M. I., Sokolov V. B., “Nekotorye problemy v optimizatsii razmescheniya bolshikh tomov pamyati”, Avtomatika i telemekhanika, 1969, no. 9, 83–91

[14] Metelskii N. N., “Ob ekstremalnykh znacheniyakh kvadratichnoi formy na simmetricheskoi gruppe”, Izv. AN Belorusskoi SSR. Ser. fiz.-mat. nauk, 1972, no. 6, 107–110

[15] Pratt V. R., “An $N\log N$ algorithm to distribute $N$ records optimally in a sequential access file”, Complexity of computer computations, Plenum, New York, 1972, 111–118 | MR

[16] Suprunenko D. A., Gruppy podstanovok, Nauka i tekhnika, Minsk, 1996