Investigation of polynomial algorithms for solving the multicriteria three-index planar assignment problem

S. A. Dichkovskaya   ; M. K. Kravtsov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 6, pp. 1077-1086

Résumé

Under certain additional conditions imposed on the coefficients of the vector objective function in the three-index planar assignment problem, a large series of computational experiments aimed at the investigation of four polynomial algorithms for finding an asymptotically optimal solution of this problem is carried out.

Bibliographie

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

[2] Burkard R. E., Frohlich K., “Some remarks on 3-dimensional assignment problems”, Methods Operat. Res., 36 (1980), 31–36 | Zbl

[3] Balas E., Landweer P., “Traffic assignment in communication satellites”, Operat. Res., 2 (1983), 141–147 | Zbl

[4] Laywine C. F., Mullen G. L., Discrete mathematics using latin squares, John Wiley Sons, New York, 1998 | MR

[5] Magos D., Mourtos I., Appa G., Polyhedral results for assignment problems, CD AM Res. Rept ISE-CDAM-2002-01

[6] Euler R., Verge H. Le, “Time-tables, polyhedra and the greedy algorithm”, Discrete Appl. Math., 65 (1996), 207–221 | DOI | MR | Zbl

[7] Frieze A. M., “Complexity of a 3-dimensional assignment problem”, Europ. J. Operat. Res., 13 (1983), 161–164 | DOI | MR | Zbl

[8] Kuzyurin H. H., “Slozhnost v srednem i zadachi tselochislennogo lineinogo programmirovaniya”, Materialy Ross. konf. “Diskretnyi analiz i issl. operatsii”, Novosibirsk, 2004, 39–40

[9] Perepelitsa V. A., “O dvukh zadachakh iz teorii grafov”, Dokl. AN SSSR, 194:6 (1970), 1269–1272

[10] Gimadi E. Kh., Glebov H. I., Serdyukov A. I., “Algoritm dlya priblizhennogo resheniya zadachi kommivoyazhera i ego veroyatnostnyi analiz”, Sibirskii matem. zhurnal. Issl. operatsii, 1:2 (1994), 8–17 | MR | Zbl

[11] Korshunov A. D., “Osnovnye svoistva sluchainykh grafov s bolshim chislom vershin i reber”, Uspekhi matem. nauk, 40:1 (1985), 107–173 | MR | Zbl

[12] Emelichev V. A., Perepelitsa V. A., “Slozhnost diskretnykh mnogokriterialnykh zadach”, Diskretnaya matem., 6:1 (1994), 3–33 | Zbl

[13] Emelichev V. A., Efimchik N. E., “Asimptoticheskii podkhod k zadache o $k$-mediane grafa”, Kibernetika i sistemnyi analiz, 1994, no. 5, 109–117 | MR | Zbl

[14] Sergienko I. V., Perepelitsa V. A., “K probleme nakhozhdeniya mnozhestv alternativ v diskretnykh mnogokriterialnykh zadachakh”, Kibernetika, 1987, no. 5, 85–93 | MR | Zbl

[15] Emelichev V. A., Perepelitsa V. A., Shungerov Kh. D., “Asimptoticheskii podkhod k mnogokriterialnoi zadache pokrytiya grafa zvezdami”, Dokl. AN BSSR, 31:5 (1985), 5–9

[16] Kravtsov M. K., Krachkovskii A. P., “Asimptoticheskaya optimalnost plana transportnoi zadachi, postroennogo metodom minimalnogo elementa”, Kibernetika i sistemnyi analiz, 1999, no. 1, 144–151 | MR | Zbl

[17] Kravtsov M. K., Krachkovskii A. P., “Asimptoticheskii podkhod k resheniyu mnogoindeksnoi aksialnoi transportnoi zadachi”, Zh. vychisl. matem. i matem. fiz., 38:7 (1998), 1133–1139 | MR | Zbl

[18] Kravtsov M. K., Krachkovskii A. P., “Asimptoticheskii podkhod k resheniyu mnogoindeksnoi aksialnoi problemy vybora”, Vestsi HAH Belarusi Ser. fiz.-matem. navuk, 1999, no. 2, 123–126 | MR

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

[20] Kravtsov M. K., Krachkovskii A. P., “O polinomialnom algoritme nakhozhdeniya asimptoticheski optimalnogo resheniya trekhindeksnoi planarnoi problemy vybora”, Zh. vychisl. matem. i matem. fiz., 41:2 (2001), 342–345 | MR | Zbl

[21] Smale S., “On the average number of steps in the simplex method of linear programming”, Math. Progr., 27:1 (1983), 241–262 | DOI | MR | Zbl

[22] Kuzyurin H. H., “Polinomialnyi v srednem algoritm v tselochislennom lineinom programmirovanii”, Sibirskii matem. zhurnal. Issl. operatsii, 1:3 (1994), 38–48 | MR | Zbl

[23] Kuzyurin H. H., “Metricheskie aspekty teorii tselochislennogo lineinogo programmirovaniya”, Diskretnaya matem., 6:4 (1994), 87–106 | MR | Zbl

[24] Kravtsov M. K., Krachkovskii A. P., “Polinomialnyi algoritm dlya mnogoindeksnoi problemy vybora”, Zh. vychisl. matem i matem. fiz., 39:6 (1999), 1041–1044 | MR | Zbl

[25] Kravtsov M. K., Krachkovskii A. P., “Zamechanie k state “Polinomialnyi algoritm dlya mnogoindeksnoi problemy vybora””, Zh. vychisl. matem. i matem. fiz., 40:9 (2000), 1440 | MR | Zbl

[26] Dichkovskaya S. A., Kravtsov M. K., “Issledovanie polinomialnykh algoritmov resheniya trekhindeksnoi planarnoi problemy vybora”, Zh. vychisl. matem. i matem. fiz., 46:2 (2006), 222–228 | MR | Zbl

[27] Kravtsov M. K., Dichkovskaya S. A., “Asimptoticheskii podkhod k resheniyu mnogokriteralnoi trekhindeksnoi planarnoi problemy vybora”, Kibernetika i sistemnyi analiz, 2004, no. 3, 24–29 | MR | Zbl

[28] Dinits E. A., Kronrod M. A., “Odin algoritm resheniya zadachi o naznacheniyakh”, Dokl. AN SSSR, 189:1 (1969), 23–25

[29] Emelichev V. A., Kravtsov M. K., “O nerazreshimosti vektornykh zadach diskretnoi optimizatsii na sistemakh podmnozhestv v klasse algoritmov lineinoi svertki kriteriev”, Dokl. RAN, 334:1 (1994), 9–11 | MR | Zbl

[30] Podinovskii V. V., Nogin V. D., Pareto-optimalnye resheniya mnogokriterialnykh zadach, Nauka, M., 1982 | MR