Abstract
We demonstrate that the linear multidimensional assignment problem with iid random costs is polynomially \({\varepsilon}\) -approximable almost surely (a.s.) via a simple greedy heuristic, for a broad range of probability distributions of the assignment costs. Specifically, conditions on discrete and continuous distributions of the cost coefficients, including distributions with unbounded support, have been established that guarantee convergence to unity in the a.s. sense of the cost ratio between the greedy solution and optimal solution. The corresponding convergence rates have been determined.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Papadimitrou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Dover, New York (1998)
Burkard R.E., Dell’Amico M., Martello S.: Assignment Problems. SIAM, Philadelphia (2009)
Berge C.: Hypergraphs: Combinatorics of Finite Sets. North-Holland, Amsterdam (1989)
Bollobás B.: Modern Graph Theory. Springer, New York (1998)
Pierskalla W.: The multidimensional assignment problem. Oper. Res. 16(2), 422–431 (1968)
Burkard R.E., Çela E.: Quadratic and three-dimensional assignments. In: Dell’Amico, M. (eds) Annotated Bibliographies in Combinatorial Optimization, pp. 373–391. Wiley, Chichester (1999)
Burkard R.E.: Selected topics on assignment problems. Discret. Appl. Math. 123(1–3), 257–302 (2002)
Karp R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Spieksma F.C.R.: Multi index assignment problems: complexity, approximation, applications. In: Pitsoulis, L., Pardalos, P.M. (eds) Nonlinear Assignment Problems: Algorithms and Applications, pp. 1–12. Kluwer, Dordrecht (2000)
Crama Y., Spieksma F.C.R.: Approximation algorithms for three-dimensional assignment problems with triangle inequalities. Eur. J. Oper. Res. 60(3), 273–279 (1992)
Balas E., Saltzman M.J.: An algorithm for the three-index assignment problem. Oper. Res. 39(1), 150–161 (1991)
Poore A.B.: Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. Comput. Optim. Appl. 3(1), 27–54 (1994)
Poore A.B. et al.: A numerical study of some data association problems arising in multitarget tracking. In: Hager, W.W. (eds) Large Scale Optimization: State of the Art, pp. 339–361. Kluwer, Dordrecht (1994)
Poore A.B., Robertson A.J.: A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems. Comput. Optim. Appl. 8(2), 129–150 (1997)
Murphey, R., Pardalos, P., Pitsoulis, L.: A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem. In: Pardalos, P.M., Du, D.-Z. (eds.) Network Design: Connectivity and Facilities Location, volume 40 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 277–302, American Mathematical Society (1998)
Murphey, R., Pardalos, P., Pitsoulis, L.: A parallel GRASP for the data association multidimensional assignment problem. In: Parallel Processing of Discrete Problems. The IMA Volumes in Mathematics and its Applications, vol. 106, pp. 159–180. Springer, Berlin (1998)
Andrijich S.M., Caccetta L.: Solving the multisensor data association problem. Nonlinear Anal. 47(8), 5525–5536 (2001)
Kravtsov V.M.: Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem. Cybern. Syst. Anal. 41(6), 940–944 (2005)
Krokhmal P., Pardalos P.M.: Random assignment problems. Eur. J. Oper. Res. 194(1), 1–17 (2009)
Burkard R.E., Fincke U.: The asymptotic probabilistic behavior of quadratic sum assignment problems 27, 73–81 (1982)
Burkard R.E., Fincke U.: Probabilistic asymptotic properties of some combinatorial optimization problems. Discret. Appl. Math. 12(1), 21–29 (1985)
Szpankowski W.: Combinatorial optimization problems for which almost every algorithm is asymptotically optimal!. Optimization 33(4), 359–367 (1995)
Krokhmal P., Grundel D., Pardalos P.: Asymptotic behavior of the expected optimal value of the multidimensional assignment problem. Math. Program. 109(2–3), 525–551 (2007)
Krokhmal, P.A., Pardalos, P.M.: Limiting optimal values and convergence rates in some combinatorial optimization problems on hypergraph matchings. In review (2009)
Feller W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, New York (1968)
Author information
Authors and Affiliations
Corresponding author
Additional information
This study was supported in part by AFOSR grant FA9550-09-1-0088.
Rights and permissions
About this article
Cite this article
Krokhmal, P.A. On optimality of a polynomial algorithm for random linear multidimensional assignment problem. Optim Lett 5, 153–164 (2011). https://doi.org/10.1007/s11590-010-0198-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-010-0198-6