Geodesic
Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 5, pp. 825-836 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For the relaxation polyhedron $M(4,n)$ in the four-index axial assignment problem of order $n$, $n\geqslant 3$, a characterization of all possible types (except for a single case) of maximum noninteger vertices, i.e., vertices with $4n-3$ fractional components is proposed. A formula enumerating all the maximum noninteger vertices of the same type in $M(4,n)$ is derived. 
@article{ZVMMF_2013_53_5_a13,
     author = {V. M. Kravtsov and M. K. Kravtsov},
     title = {Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {825--836},
     year = {2013},
     volume = {53},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a13/}
}
TY  - JOUR
AU  - V. M. Kravtsov
AU  - M. K. Kravtsov
TI  - Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2013
SP  - 825
EP  - 836
VL  - 53
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a13/
LA  - ru
ID  - ZVMMF_2013_53_5_a13
ER  - 
%0 Journal Article
%A V. M. Kravtsov
%A M. K. Kravtsov
%T Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2013
%P 825-836
%V 53
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a13/
%G ru
%F ZVMMF_2013_53_5_a13
V. M. Kravtsov; M. K. Kravtsov. Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 5, pp. 825-836. http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a13/

[1] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981 | MR

[2] Arbib C., Pacciarelli D., Smriglio S. A., “Three-dimensional matching model for perishable production scheduling”, Discrete Appl. Math., 92 (1999), 1–15 | DOI | MR | Zbl

[3] Grama Y., Oerlemans A., Spieksma F., Production planning in automated manufacturing, Springer-Verlag, 1996

[4] Poore A. B., “Multidimensional assignment formulation of data association problems arising from multitarget and multisensory tracking”, Comput. Optimiz. and Appl., 3 (1994), 27–54 | DOI | MR

[5] Kravtsov V. M., “O kharakterizatsii netselochislennykh vershin relaksatsionnogo mnogogrannika mnogoindeksnoi aksialnoi zadachi o naznacheniyakh”, Zh. vychisl. matem. i matem. fiz., 50:9 (2010), 1697–1708 | MR | Zbl

[6] Karp R., “Reducibility among combinatiorial problems”, Complexity of Computer Computations, eds. Miller R., Trahtcher J., Plenum Press, 1972, 85–103 | DOI | MR

[7] Burkard R., Rudolf R., Woeginger G., “Three-dimensional axial assignment problems with decomposable cost-coefficients”, Discrete Appl. Math., 65 (1996), 123–140 | DOI | MR

[8] Balas E., Saltzman M. J., “Facets of the three-index assignment polytope”, Discrete Appl. Math., 23 (1989), 201–229 | DOI | MR | Zbl

[9] Balas E., Qi Z., “Linear time separation algorithms for the three-index assignment polytope”, Discrete Appl. Math., 43 (1993), 1–12 | DOI | MR | Zbl

[10] Magos D., Mourtos I., Appa G., Polychedral results for assignment problems, CDAM Research Report LSE-CDAM-2002-01, April 19, 2002, 32 pp.

[11] Kravtsov M. K., Kravtsov V. M., Lukshin E. V., “O netselochislennykh vershinakh mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Diskr. matem., 13:2 (2001), 120–143 | DOI | MR | Zbl

[12] Kravtsov M. K., Kravtsov V. M., Lukshin E. V., “O chisle netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Vestsi NAN Belarusi. Ser. fiz.-matem. navuk, 2000, no. 4, 59–65 | MR

[13] Kravtsov M. K., Lukshin E. V., “O netselochislennykh vershinakh mnogogrannika trekhindeksnoi aksialnoi transportnoi zadachi”, Avtomatika i telemekhanika, 2004, no. 3, 71–79 | MR | Zbl

[14] Kravtsov M. K., Lukshin E. V., “Polyhedral combinatorics of multi-index axial transportation problems”, Europ. J. operat. research., 2008, no. 189, 920–938 | DOI | MR | Zbl

[15] Kravtsov V. M., “Kombinatornye svoistva netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Kibernetika i sistemnyi analiz, 2007, no. 1, 33–44 | MR | Zbl

[16] Kravtsov V. M., “O novykh svoistvakh maksimalno netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Izv. vyssh. uchebn. zavedenii. Matematika, 2004, no. 12, 37–45 | MR

[17] Kravtsov V. M., “Ob odnom tipe maksimalno netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Vestnik BGU. Ser. 1, 2005, no. 3, 83–90 | MR | Zbl

[18] Kravtsov M. K., Kravtsov V. M., Lukshin E. V., “O tipakh $(3n-2)$-netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi vybora”, Izv. vyssh. uchebn. zavedenii. Matematika, 2002, no. 12, 84–90 | MR | Zbl

[19] Kravtsov V. M., “O maksimalno netselochislennykh vershinakh mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Avtomatika i telemekhanika, 2004, no. 3, 62–70 | MR | Zbl

[20] Emelichev V. A., Kravtsov M. K., “Poliedralnye aspekty mnogoindeksnykh aksialnykh transportnykh zadach”, Diskr. matem., 3:2 (1991), 3–24

[21] Kravtsov V. M., “Otsenka snizu diametra relaksatsionnogo mnogogrannika mnogoindeksnoi aksialnoi zadachi o naznacheniyakh”, Sb. nauch. tr., Ekonomika, modelirovanie, prognozirovanie, 3, NIEI Ministerstva ekonomiki Respubliki Belarus, Mn., 2009, 218–232

[22] Kravtsov V. M., “Kharakterizatsiya tipov maksimalno netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Izv. vyssh. uchebn. zavedenii. Matematika, 2006, no. 12, 65–68 | MR

[23] Kravtsov V. M., “O kharakterizatsii tipov maksimalno netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Zh. vychisl. matem. i matem. fiz., 46:10 (2006), 1908–1912 | MR

[24] Kravtsov V. M., “Kharakterizatsiya tipov polnostyu netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Vestnik BGU. Ser. 1, 2007, no. 1, 108–113 | MR

[25] Kravtsov M. K., Lukshin E. V., “O netselochislennykh vershinakh mnogogrannika mnogoindeksnoi aksialnoi zadachi vybora”, Izv. vyssh. uchebn. zavedenii. Matematika, 1999, no. 12, 65–70 | MR | Zbl