Geodesic
On a characterization of noninteger vertices of the relaxational polyhedron in the multi-index axial assignment problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 9, pp. 1697-1708 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Theorems about the characterization and exponential growth of the denominators of fractional components of noninteger vertices of the relaxation polyhedron in the multi-index axial assignment problem are proved. They made it possible to obtain new lower bounds on the number of noninteger vertices of this polyhedron and to refute the conjecture on the estimate of the ratio of the number of integer vertices to the number of all vertices of the multi-index axial transportation polyhedron determined by integer vectors. 
@article{ZVMMF_2010_50_9_a11,
     author = {V. M. Kravtsov},
     title = {On a characterization of noninteger vertices of the relaxational polyhedron in the multi-index axial assignment problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1697--1708},
     year = {2010},
     volume = {50},
     number = {9},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_9_a11/}
}
TY  - JOUR
AU  - V. M. Kravtsov
TI  - On a characterization of noninteger vertices of the relaxational polyhedron in the multi-index axial assignment problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 1697
EP  - 1708
VL  - 50
IS  - 9
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_9_a11/
LA  - ru
ID  - ZVMMF_2010_50_9_a11
ER  - 
%0 Journal Article
%A V. M. Kravtsov
%T On a characterization of noninteger vertices of the relaxational polyhedron in the multi-index axial assignment problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 1697-1708
%V 50
%N 9
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_9_a11/
%G ru
%F ZVMMF_2010_50_9_a11
V. M. Kravtsov. On a characterization of noninteger vertices of the relaxational polyhedron in the multi-index axial assignment problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 9, pp. 1697-1708. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_9_a11/

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

[2] Karp R., “Reducibility among combinatorial problems”, Complexity Comput. Computs., Plenum Press, New York, 1972, 86–103 | MR

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

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

[5] Grama Y., Oerlemans A., Spieksma F., Production planning in automated manufacturing, Springer, Berlin, 1996

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

[7] Kravtsov V. M., “Polinomialnye algoritmy nakhozhdeniya asimptoticheski optimalnogo resheniya mnogoindeksnoi aksialnoi problemy vybora”, Kibernetika i sistemnyi analiz, 2005, no. 6, 176–181 | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

[20] Kravtsov M. K., Kravtsov V. M., Lukshin E. V., “O chisle $r$-netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi vybora”, Izv. vuzov. Matematika, 2000, no. 12, 89–92 | MR | Zbl

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

[22] Shevchenko V. N., Kachestvennye voprosy tselochislennogo programmirovaniya, Nauka, M., 1995 | MR | Zbl