Random Assignment Problems

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 f({\bf x})
subject to
\sum_{i=1}^n x_{ij} = 1,
\sum_{j=1}^n x_{ij} = 1,
x_{ij} \in \{0,1\}.

Alternatively, one can think of this as finding a perfect matching in a complete bipartite graph that minimizes the objective f({\bf x}).  For the standard assignment problem the objective is the sum of the assignment costs f({\bf x}) = \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}, where c_{ij} 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 c_{ij} be random variables. Formally, let c^*_n denote the optimal value of a particular n \times n assignment problem.  Now I’ll briefly discuss what is known about E[c^*_n] for three of the most common forms of the objective f({\bf x}).

We’ll start, naturally, with the linear sum f({\bf x}) = \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}.  Back in 1969 Donath [4] conjectured, based on experimental evidence, that if the costs are iid uniform (0,1) random variables then E[c^*_n] converges to something around 1.6 as n \to \infty.  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 \frac{\pi^2}{6}.  (Yet another place where \zeta(2) 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 E[c^*_n] is exactly \sum_{k=1}^n \frac{1}{k^2}.

Perhaps the second-most common form of the objective after the linear sum \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} is the bottleneck objective:  \min \max_{1 \leq i,j \leq n} c_{ij} x_{ij}.  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 \sup \{x | F(x) < 1\} < \infty then \lim_{n \to \infty} E[c_n^*] = \inf\{x | F(x) > 0\}.  In particular, for the continuous uniform(0,1) case, E[c_n^*] \to 0 as n \to \infty.  Pferschy also gave the asymptotic bounds

\displaystyle \frac{\log n + \gamma}{n} + O\left(\frac{(\log n)^2}{n^2}\right) \leq E[c_n^*] \leq \frac{4\log n}{n} + O\left(\frac{1}{n}\right).

The latter were improved by me [10] to

\displaystyle E[c_n^*] = \frac{\log n + \log 2 + \gamma}{n} + O\left(\frac{(\log n)^2}{n^{7/5}}\right).

I managed to obtain the variance as well:

\displaystyle Var[c_n^*] = \frac{\zeta(2) - 2(\log 2)^2}{n^2} + O\left( \frac{(\log n)^2}{n^{7/3}}\right).

A third common form of the objective is the quadratic objective \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \sum_{l=1}^n a_{ij} b_{kl} x_{ik} x_{jl}.  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 a_{ij} and b_{kl} are iid continuous uniform(0,1) then the ratio of c^*_n and the worst possible solution c_n^\prime converges to 1 in probability as n \to \infty.  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

  1. David J. Aldous, “The \zeta(2) limit in the random assignment problem,” Random Structures and Algorithms 18, pp. 381-418, 2001.
  2. Rainer Burkard, Mauro Dell’Amico, and Silvano Martello, Assignment Problems, SIAM, 2009.
  3. R. E. Burkard and U. Fincke, “The asymptotic probabilistic behavior of quadratic sum assignment problems,” Zeitschrift für Operations Research 27, pp. 73-81, 1982.
  4. W. E. Donath, “Algorithm and average-value bounds for assignment problems,” IBM Journal of Research and Development 13, pp. 380-386, 1969.
  5. Pavlo A. Krokhmal and Panos M. Pardalos, “Random assignment problems,” European Journal of Operations Research 194, pp. 1-17, 2009.
  6. 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.
  7. M. Mézard and G. Parisi, “On the solution of the random link matching problem,” Journal de Physique 48 (9), pp. 1451-1459, 1987.
  8. 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.
  9. U. Pferschy, “The random linear bottleneck assignment problem,” RAIRO – Operations Research 30 (2), pp. 127-142, 1996.
  10. Michael Z. Spivey, “Asymptotic moments of the bottleneck assignment problem,” Mathematics of Operations Research 36 (2), pp. 205-226, 2011.
Advertisements
This entry was posted in asymptotics, combinatorial optimization, probability. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s