Asymptotic Properties of Random Multidimensional Assignment Problems
Tóm tắt
The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.
Tài liệu tham khảo
Grundel, D. A., Oliveira, C. A. S., Pardalos, P. M., and Pasiliao, E., Asymptotic Results for Random Multidimensional Assignment Problems, Technical Report, Industrial and Systems Engineering Department, University of Florida, Gainesville, Florida, 2003.
Garey, M. R., and Johnson, D. S., Computers and Intractability:A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, California, 1979.
Pierskalla, W., The Multidimensional Assignment Problem. Operations Research, Vol. 16, pp. 422-431, 1968.
Pardalos, P., Murphey, R., and Pitsoulis, L., A Greedy Randomized Adaptive Search Procedure for the Multitarget Multisensor Tracking Problem, Network Design:Connectivity and Facility Location, Edited by D. Z. Du and P. Pardalos, Series on Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, Rhode Island, Vol 40, pp. 277-302, 1997.
Andrijich, S. M., and Caccetta, L., Solving the Multisensor Data Association Problem, Nonlinear Analysis, Vol. 47, pp. 5525-5536, 2001.
Veenman, C., Hendriks, E., and Reinders, M., A Fast and Robust Point Tracking Algorithm, Proceedings of the 5th IEEE International Conference on Image Processing, Chicago, Illinois, pp. 653-657, 1998.
Pusztaszeri, J., Rensing, P., and Liebling, T., Tracking Elementary Particles Near Their Primary Vertex: A Combinatorial Approach, Journal of Global Optimization, Vol. 9, pp. 41-64, 1996.
Pardalos, P., and Pitsoulis, L., Editors, Nonlinear Assignment: Problems, Algorithms, and Applications, Kluwer, Dordrecht, Holland, 2000.
Aldous, D., Asymptotics in the Random Assignment Problem, Probability Theory and Related Fields, Vol. 93, pp. 507-534, 1992.
Coppersmith, D., and Sorkin, G., Constructive Bounds and Exact Expectations for the Random Assignment Problem, Random Structures and Algorithms, Vol. 15, pp. 133-144, 1999.
Coppersmith, D., and Sorkin, G., On the Expected Incremental Cost of a Minimum Assignment, Technical Report, T. J. Watson IBM Research Center, 1999.
Karp, R., An Upper Bound on the Expected Cost of an Optimal Assignment, Discrete Algorithms and Complexity:Proceedings of the Japan-US Joint Seminar, Edited by D. Johnson et al, Academic Press, New York, NY, pp. 1-4, 1987.
Pardalos, P., and Ramakrishnan, K., On the Expected Optimal Value of Random Assignment Problems:Experimental Results and Open Questions, Computational Optimization and Applications, Vol. 2, pp. 261-271, 1993.
Alon, N., and Spencer, J., The Probabilistic Method, 2nd Edition, Inter-science Series in Discrete Mathematics and Optimization, John Wiley, New York, NY, 2000.
David, H., Order Statistics, John Wiley and Sons, New York, NY, 1970.
Cramér, H., Mathematical Methods of Statistics. Princeton University Press, Princeton, New Jersey, 1957.
Burkard, R. E., and Cela, E., Linear Assignment Problems and Extensions, Handbook of Combinatorial Optimization, Supplement Volume A, Edited by D. Z. Du and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Holland, pp. 75-149, 1999.