The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations

E. Kh. Gimadi ; Yu. V. Glazkov ; O. Yu. Tsidulko

Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 1, pp. 15-29.

Résumé

We study the $m$-planar $3$-dimensional assignment problem on one-cycle permutations. In other words, it is the $m$-peripatetic salesman problem ($m$-PSP) with different weight functions for each salesman. The problem is NP-hard for $m\ge1$. We introduce a polynomial approximation algorithm suggested for $1$ with time complexity $O(mn^2)$. The performance ratios of the algorithm are established for input data (elements of $(m\times n\times n)$-matrix) which are assumed to be independent and identically distributed random variables on $[a_n,b_n]$, where $0$. If the distribution is uniform or dominates the uniform distribution, conditions on $a_n,b_n$ and $m$ are obtained for the asymptotic optimality of the algorithm. Ill. 1, bibliogr. 26.

Détail

Keywords: $m$-planar $3$-dimensional assignment problem, $m$-PSP with different weight functions, asymptotic optimality.
Mots-clés : one-cycle permutations, polynomial approximation algorithm

Bibliographie

[1] Baburin A. E., Gimadi E. Kh., “On the asymptotic optimality of an algorithm for solving the maximum $m$-PSP in a multidimensional Euclidean space”, Proc. Steklov Inst. Math., 272, 2011, S1–S13 | DOI | Zbl

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

[3] Gimadi E. Kh., “Asimptoticheski tochnyi podkhod k resheniyu mnogoindeksnoi aksialnoi zadachi o naznachenii”, Tr. XI Mezhdunar. Baikalskoi shkoly-seminara, Plenarnye doklady, Izd. SEI SO RAN, Irkutsk, 1998, 62–65

[4] Gimadi E. Kh., Glazkov Yu. V., “An asymptotically exact algorithm for one modification of planar three-index assignment problem”, J. Appl. Industr. Math., 1:4 (2007), 442–452 | DOI | MR | Zbl

[5] Gimadi E. Kh., Korkishko N. M., “Ob odnom algoritme resheniya trëkhindeksnoi aksialnoi zadachi o naznacheniyakh na odnotsiklicheskikh podstanovkakh”, Diskret. analiz i issled. operatsii. Ser. 1, 10:2 (2003), 56–65 | MR | Zbl

[6] Gimadi E. Kh., Ivonina E. V., “Approximation algorithms for the maximum 2-peripatetic salesman problem”, J. Appl. Industr. Math., 6:3 (2012), 295–305 | DOI | MR | MR

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

[8] Glebov A. N., Zambalaeva D. Zh., “A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem”, J. Appl. Industr. Math., 6:3 (2012), 69–89 | DOI | MR | Zbl

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

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

[11] Emelichev V. A., Kovalev M. M., Kravtsov M. M., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981, 342 pp. | MR | Zbl

[12] Kravtsov M. K., Krachkovskii A. P., “O polinomialnom algoritme nakhozhdeniya asimptoticheski optimalnogo resheniya trëkhindeksnoi planarnoi problemy vybora”, Zhurn. vychisl. matematiki i mat. fiziki, 41:2 (2001), 342–345 | MR | Zbl

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

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

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

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

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

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

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

[20] Gimadi E. Kh., “On some probability inequalities in some discrete optimization problems”, Oper. Res. – 2005, Proc., Springer-Verl., Berlin, 2006, 283–289 | DOI | Zbl

[21] Gimadi E. Kh., Kairan N. M., “Multi-index assignment problem: an asymptotically optimal approach”, Proc. 8th IEEE Int. Conf. Emerging Technologies and Factory Automation (Antibes – Juan-les-Pins, France, 15–18 October 2001), Institute of Electrical and Electronics Engineers, Inc., Paris, 2001, 707–710

[22] Gimadi E. Kh., Korkishko N. M., “On some modifications of the three-index planar assignment problem”, Discrete optimization methods in production and logistics, 2nd Int. Workshop (Omsk – Irkutsk, July 20–27, 2004), Proc. DOM'2004, Nasledie Dialog-Sibir Pbs., Omsk, 2004, 161–165

[23] Krarup J., “The peripatetic salesman and some related unsolved problems”, Comb. Programming: Methods and Applications, Proc. NATO Adv. Study Inst. (Versailles, 1974), Reidel, Dordrecht, 1975, 173–178 | MR

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

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

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