Geodesic
On solvability of the axial $8$-index assignment problem on one-cycle permutations
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 5, pp. 66-83.

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

We study the axial $8$-index assignment problem on one-cycle permutations. For a long time the question of solvability of its set of constraints for one-cycle permutations of length $n$ in the case of $8$ indices remained open. We prove that the set of constraints have a solution if $n$ is odd and greater than $87$. Ill. 4, bibliogr. 11.
Keywords: multi-index assignment problem, axiallity, solvability
Mots-clés : one-cycle permutation. 
@article{DA_2013_20_5_a5,
     author = {O. Yu. Tsidulko},
     title = {On solvability of the axial $8$-index assignment problem on one-cycle permutations},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {66--83},
     publisher = {mathdoc},
     volume = {20},
     number = {5},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_5_a5/}
}
TY  - JOUR
AU  - O. Yu. Tsidulko
TI  - On solvability of the axial $8$-index assignment problem on one-cycle permutations
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 66
EP  - 83
VL  - 20
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_5_a5/
LA  - ru
ID  - DA_2013_20_5_a5
ER  - 
%0 Journal Article
%A O. Yu. Tsidulko
%T On solvability of the axial $8$-index assignment problem on one-cycle permutations
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 66-83
%V 20
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_5_a5/
%G ru
%F DA_2013_20_5_a5
O. Yu. Tsidulko. On solvability of the axial $8$-index assignment problem on one-cycle permutations. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 5, pp. 66-83. http://geodesic.mathdoc.fr/item/DA_2013_20_5_a5/

[1] Gimadi E. Kh., Ivonina E. V., “Priblizhënnye algoritmy resheniya zadachi o dvukh kommivoyazhërakh na maksimum”, Diskret. analiz i issled. operatsii, 19:1 (2012), 17–32 | MR

[2] Gimadi E. Kh., Korkishko N. M., Serdyukov A. I., “O razreshimosti mnogoindeksnoi aksialnoi zadachi o naznacheniyakh na odnotsiklicheskikh podstanovkakh”, Izv. vuzov. Matematika, 2000, no. 12, 21–26 | MR | Zbl

[3] Glebov A. N., Gordeeva A. V., Zambalaeva D. Zh., “Algoritm s otsenkoi 7/5 dlya zadachi o dvukh kommivoyazhërakh na minimum s razlichnymi vesovymi funktsiyami”, Sib. elektron. mat. izv., 8 (2011), 296–309 | MR

[4] Glebov A. N., Zambalaeva D. Zh., “Polinomialnyi algoritm s otsenkoi tochnosti 7/9 dlya zadachi o dvukh kommivoyazhërakh na maksimum”, Diskret. analiz i issled. operatsii, 18:4 (2011), 17–48 | MR | Zbl

[5] Glebov A. N., Zambalaeva D. Zh., “Priblizhënnyi algoritm resheniya zadachi o dvukh kommivoyazhërakh na minimum s razlichnymi vesovymi funktsiyami”, Diskret. analiz i issled. operatsii, 18:5 (2011), 11–37 | MR | Zbl

[6] Gimadi E. Kh., Serdyukov A. I., “Aksialnye zadachi o naznachenii i kommivoyazhëra: bystrye priblizhënnye algoritmy i ikh veroyatnostnyi analiz”, Izv. vuzov. Matematika, 1999, no. 12(451), 19–25 | MR | Zbl

[7] Korkishko N. M., Priblizhennye algoritmy resheniya nekotorykh mnogoindeksnykh zadach o naznacheniyakh, Dis. $\dots$ kand. fiz.-mat. nauk: 01.01.09, Novosibirsk, 2003, 116 pp.

[8] Burkard R., Dell'Amico M., Martello S., Assignments, SIAM, Philadelphia, 2009, 382 pp. | MR | Zbl

[9] Fon-Der-Flaass D. G., “Array of distinct representatives – a very simple NP-complete problem”, Discrete Math., 171:1–3 (1997), 295–298 | DOI | MR | Zbl

[10] Frieze A. M., “Complexity of a 3-dimensional assignment problem”, Eur. J. Oper. Res., 13:2 (1983), 161–164 | DOI | MR | Zbl

[11] Spieksma F. C. R., “Multi index assignment problems: complexity, approximation, applications”, Nonlinear assignment problems, algorithms and applications, Kluwer Acad. Publ., Dordrecht, 2000, 1–12 | DOI | MR | Zbl