Abstract.
An assignment problem is the optimization problem of finding, in an m by n matrix of nonnegative real numbers, k entries, no two in the same row or column, such that their sum is minimal. Such an optimization problem is called a random assignment problem if the matrix entries are random variables. We give a formula for the expected value of the optimal k-assignment in a matrix where some of the entries are zero, and all other entries are independent exponentially distributed random variables with mean 1. Thereby we prove the formula 1+1/4+1/9+\...+1/k 2 conjectured by G. Parisi for the case k=m=n, and the generalized conjecture of D. Coppersmith and G. B. Sorkin for arbitrary k, m and n.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldous, D.: Asymptotics in the random assignment problem. Pr. Th. Related Fields 93, 507–534 (1992)
Aldous, D.: The ζ(2) limit in the random assignment problem. Random Structures Algorithms 18 (4), 381–418 (2001)
Alm, S.E., Sorkin, G.B.: Exact expectations and distributions in the random assignment problem. Combin. Probab. Comput. 11 (3), 217–248 (2002)
Beveridge, A., Frieze, A.M., McDarmid Colin J.H.: Random minimum length spanning trees in regular graphs. Combinatorica 18, 311–333 (1998)
Buck, M.W., Chan, C.S., Robbins, D.P.: On the expected value of the minimum assignment. Random Structures Algorithms. 21 (1), 33–58 (2002)
Coppersmith, D., Sorkin, G.B.: Constructive Bounds and Exact Expectations For the Random Assignment Problem. Random Structures Algorithms 15, 133–144 (1999)
Coppersmith, D., Sorkin, G.B.: On the expected incremental cost of a minimum assignment. In: Contemporary Mathematics, B. Bollobás, (ed.), Vol. 10 of Bolyai Society Mathematical Studies, Springer
Eriksson, H., Eriksson, K., Sjöstrand, J.: Exact expectation for random graphs and assignments. Proceedings of FPSAC 2001, Arizona
Frieze, A.M., McDarmid Colin, J.H.: On random minimum spanning trees, Combinatorica 9, 1989
Frieze, A.M.: On the value of a random minimum spanning tree problem. Disc Appl. Math. 10, 47–56 (1985)
Goemans, M.X., Kodialam, M.S.: A lower bound on the expected cost of an optimal assignment. Math. Oper. Res. 18, 267–274 (1993)
Karp, R.M.: An upper bound on the expected cost of an optimal assignment. In Discrete Algorithms and Complexity: Proceedings of the Japan-U.S. Joint Seminar, Academic Press, 1987, pp. 1–4
Lazarus, A.: Certain expected values in the random assignment problem. Oper. Res. Lett. 14, 207–214 (1993)
Linusson, S., Wästlund, J.: A generalization of the random assignment problem. Unpublished manuscript. arXiv:math.CO/0006146
Lovász, L., Plummer, M.D.: Matching Theory, North-Holland 1986
Mézard, M., Parisi, G.: Replicas and optimization. J. Phys. Lett. 46, 771–778 (1985)
Mézard, M., Parisi, G.: On the solution of the random link matching problems. J. Phys. Lett. 48, 1451–1459 (1987)
Nair, C.: Towards the resolution of Coppersmith-Sorkin conjectures. Proceedings of the 40th annual Allerton conference on communication, control and computing, 2002
Nair, C., Prabhakar, B., Sharma, M.: A proof of the conjecture due to Parisi for the finite random assignment problem, available at http://www.stanford.edu/∼balaji/ rap.html
Chandra Nair, Balaji Prabhakar, Mayank Sharma, Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Fininte Random Assignment Problem, Proceedings of IEEE FOCS, 2003
Olin, Birgitta, Asymptotic properties of the random assignment problem, Ph.D. thesis, Kungl Tekniska Högskolan, Stockholm, Sweden, 1992
Pardalos, P.M., Ramakrishnan, K.G.: On the expected optimal value of random assignment problems: Experimental results and open questions. Comput. Optim. Appl. 2, 261–271 (1993)
Parisi, G.: A conjecture on random bipartite matching. Physics e-Print archive, http://xxx.lanl.gov/ps/cond-mat/9801176, January 1998
Walkup, D.W.: On the expected value of a random assignment problem. SIAM J. Comput. 8, 440–442 (1979)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Linusson, S., Wästlund, J. A proof of Parisi’s conjecture on the random assignment problem. Probab. Theory Relat. Fields 128, 419–440 (2004). https://doi.org/10.1007/s00440-003-0308-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-003-0308-9