An asymptotically exact algorithm for one modification of planar three-index assignment

E. Kh. Gimadi ; Yu. V. Glazkov

Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 1, pp. 10-26.

Résumé

An $m$-layer three-index assignment problem is considered which is a modification of the classical planar three-index assignment problem. This problem is NP-hard for $m\geqslant2$. An approximate algorithm, solving this problem for $1$, is suggested. The bounds on its quality are proved in the case when the input data (the elements of an $m\times n\times n$ matrix) are independent identically distributed random variables whose values lie in the interval $[a_n,b_n]$, where $b_n>a_n>0$. The time complexity of the algorithm is $O(mn^2+m^{7/2})$. It is shown that in the case of a uniform distribution (and also a distribution of minorized type) the algorithm is asymptotically exact if $m=\Theta(n^{1-\theta})$ and $b_n/a_n=o(n^\theta)$ for every constant $\theta$, $0\theta1$.

Bibliographie

[1] Ageev A. A., Baburin A. E., Gimadi E. Kh., Korkishko N. M., “Algoritmy s konstantnymi otsenkami tochnosti dlya otyskaniya dvukh reberno neperesekayuschikhsya gamiltonovykh tsiklov ekstremalnogo vesa”, Vserossiiskaya konferentsiya “Problemy optimizatsii i ekonomicheskie prilozheniya”. Materialy konferentsii (Omsk, 1–5 iyulya 2003 g.), Izdatelstvo Nasledie, Omsk, 2003, 9–12

[2] Baburin A. E., Gimadi E. Kh., Korkishko N. M., “Priblizhennye algoritmy dlya nakhozhdeniya dvukh reberno neperesekayuschikhsya gamiltonovykh tsiklov minimalnogo vesa”, Diskret. analiz i issled. operatsii. Ser. 2, 11:1 (2004), 11–25 | MR | Zbl

[3] Voznyuk I. P., Gimadi E. Kh., Filatov M. Yu., “Asimptoticheski tochnyi algoritm dlya resheniya zadachi razmescheniya s ogranichennymi ob'emami proizvodstva”, Diskret. analiz i issled. operatsii. Ser. 2, 8:2 (2001), 3–16 | MR | Zbl

[4] Gimadi E. Kh., “Asimptoticheski tochnyi podkhod k resheniyu mnogoindeksnoi aksialnoi zadachi o naznachenii”, Trudy XI Mezhd. Baikalskoi shkoly-seminara. Plenarnye doklady, Irkutsk, 1998, 62–65

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

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

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

[8] Ore O., Teoriya grafov, Nauka, M., 1980 | MR

[9] Petrov V. V., Predelnye teoremy dlya summ nezavisimykh sluchainykh velichin, Nauka, M., 1987 | MR

[10] Baburin A. Y., Gimadi E. Kh., Korkishko N. M., “Algorithms with performance guarantees for a metric problem of finding two edge-disjoint Hamiltonian circuits of minimum total weight”, Operation Research Proceedings 2003, Springer, Berlin, 2004, 316–323 | MR | Zbl

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

[12] Balas E., Saltzman M. J., “An algorithm for the three-index assignment problem”, Oper. Res., 39:1 (1991), 150–161 | DOI | MR | Zbl

[13] Croce F. D., Pashos V. Th., Calvo R. W., “Approximating the 2-peripatetic salesman problem”, 7th Workshop on models and algorithms for planning and scheduling problems, MAPS 2005 (Siena, Italy, June 6–10), 2005, 114–116

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

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

[16] Gimadi E. Kh., “On some probability inequalities in some discrete optimization problems”, Operation Research Proceedings 2005 in 2006 (to appear)

[17] Gimadi E. Kh., Kairan N. M., “Multi-index assignment problem: an asymptotically optimal approach”, Proc. 8th IEEE Intern. Conf. on emerging technologies and factory automation (Antibes–Juan les Pins, France, 2001), IEEE, NY, 2001, 707–710

[18] Gimadi E. Kh., Korkishko N. M., “On some modifications of three index planar assignment problem”, Discrete optimization methods in production and logistics. The second int. workshop, Proc. DOM'2004 (Omsk, July 20–27, 2004), Omsk, 2004, 161–165

[19] Hopcroft J. E., Karp R. M., “An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs”, SIAM J. Comput., 2:4 (1973), 225–231 | DOI | MR | Zbl

[20] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, Proc. NATO Advanced Study Inst. (Versailles, 1974), Reidel, Dordrecht, 1975, 173–178 | MR

[21] Magos D., “Tabu search for the planar three-index assignment problem”, J. Global Optim., 8:1 (1996), 35–48 | DOI | MR | Zbl

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

[23] Vlach M., “Branch and bound method for the three-index assignment problem”, Ekonomicko-Matematicky Obzor, 3 (1967), 181–191 | MR