The most fundamental problem in combinatorial optimization is probably the assignment problem. Here we have, say, a set of *n* resources and a set of *n* tasks, and we want to assign each resource to exactly one task and exactly one task to each resource so that some objective function is minimized. Mathematically, this can be formulated as

Minimize

subject to

,

,

.

Alternatively, one can think of this as finding a perfect matching in a complete bipartite graph that minimizes the objective . For the standard assignment problem the objective is the sum of the assignment costs , where is the cost for assigning resource *i* to task *j*.

There are lots of things one could say about assignment problems. For this post I’m going to focus on what happens to the expected optimal objective function value when you let the costs be random variables. Formally, let denote the optimal value of a particular assignment problem. Now I’ll briefly discuss what is known about for three of the most common forms of the objective .

We’ll start, naturally, with the linear sum . Back in 1969 Donath [4] conjectured, based on experimental evidence, that if the costs are iid uniform (0,1) random variables then converges to something around 1.6 as . Various upper and lower bounds were proved in the next three decades, and in the 1980s Mézard and Parisi [7] used the replica method from statistical physics to show that the exact value should be . (Yet another place where shows up!) This was not formally proved, though, until Aldous’s 2001 paper [1], where he also shows that the same limiting value holds for costs from an exponential(1) distribution. Within a few years, Linusson and Wästlund [6] and Nair, Prabhakar, and Sharma [8] independently proved that if the costs are iid exponential(1) then is exactly .

Perhaps the second-most common form of the objective after the linear sum is the bottleneck objective: . This bottleneck assignment problem occurs, say, when you have *n* jobs to be completed on *n* machines, and you want to minimize the time that the last machine completes its job. For this problem Pferschy [9] showed that if costs are chosen independently from a continuous distribution having cumulative distribution function *F* such that then . In particular, for the continuous uniform(0,1) case, as . Pferschy also gave the asymptotic bounds

The latter were improved by me [10] to

I managed to obtain the variance as well:

A third common form of the objective is the quadratic objective . This quadratic assignment problem arises in the context of facility location. The behavior in the quadratic case is quite different. Burkard and Fincke [3] showed that if and are iid continuous uniform(0,1) then the ratio of and the worst possible solution converges to 1 in probability as . An implication of this surprising result is that if *n* is sufficiently large then one can, with high probability, obtain an approximately optimal solution simply by finding a feasible one!

For more discussion of these results, as well as extensions, see the text [2] by Burkard, Dell’Amico, and Martello or the recent survey paper by Krokhmal and Pardalos [5].

**References**

- David J. Aldous, “The limit in the random assignment problem,”
*Random Structures and Algorithms*18, pp. 381-418, 2001. - Rainer Burkard, Mauro Dell’Amico, and Silvano Martello,
*Assignment Problems*, SIAM, 2009. - R. E. Burkard and U. Fincke, “The asymptotic probabilistic behavior of quadratic sum assignment problems,”
*Zeitschrift f*27, pp. 73-81, 1982.*ü*r Operations Research - W. E. Donath, “Algorithm and average-value bounds for assignment problems,”
*IBM Journal of Research and Development*13, pp. 380-386, 1969. - Pavlo A. Krokhmal and Panos M. Pardalos, “Random assignment problems,”
*European Journal of Operations Research*194, pp. 1-17, 2009. - Svante Linusson and Johan Wästlund, “A proof of Parisi’s conjecture on the random assignment problem,”
*Probability Theory and Related Fields*128 (3), pp. 419-440, 2004. - M. Mézard and G. Parisi, “On the solution of the random link matching problem,”
48 (9), pp. 1451-1459, 1987.*Journal de Physique* - Chandra Nair, Balaji Prabhakar, and Mayank Sharma, “Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures,”
*Random Structures and Algorithms*27 (4), pp. 413-444, 2005. - U. Pferschy, “The random linear bottleneck assignment problem,”
*RAIRO – Operations Research*30 (2), pp. 127-142, 1996. - Michael Z. Spivey, “Asymptotic moments of the bottleneck assignment problem,”
*Mathematics of Operations Research*36 (2), pp. 205-226, 2011.