4
$\begingroup$

Edited

I got this problem when reading Goeman's lecture notes http://www-math.mit.edu/~goemans/18433S11/matching-notes.pdf

Problem: Exercise 1-16. ...Take a complete bipartite graph with n vertices on each side of the bipartition, and let us assume that all $c_{ij}$ (for i, j $\in$ {1, · · · , n}) are all independent uniform random variables between 0 and 1. Take 5 different values for n (the largest being a few hundreds) and for each compute the minimum cost assignment value for 5 instances. Any guess on how this value increases as n goes to infinity. Any guess on how this value increases as n goes to infinity. Does it seem to converge? To what value? Surprised? (Yes, you should be, and it is normal that you do not understand why.)

Question: Anyone know where the minimum cost will converge to, and the reason?

  • 3
    This paper seems to be relevant: Aldous, Min, *The $\zeta(2)$ Limit in the Random Assignment Problem* (2000).2011-12-06
  • 0
    Is there any reason you deleted *"Take 5 different values for n (the largest being a few hundreds) and for each compute the minimum cost assignment value for 5 instances*" from the middle of the question? $n$ does not converge, but the minimum cost assignment might, and it could be helpful to say what that was.2011-12-06
  • 0
    A very simple approximation giving $O(\ln n)$ is greedy method: match the first item with minimum possible cost (expected value $\frac{1}{n+1}$), second ($\frac{1}{n}$) etc., that gives $\frac{1}{n+1} + \dots + \frac{1}{2}$.2011-12-06
  • 0
    @Henry Sorry for that. Yes I mean the min cost instead of n.2011-12-06
  • 0
    @sdcvvc The limit of min cost of optimal solution should be bounded, but the greedy scheme isn't. I think I miss your point.2011-12-06
  • 0
    I was giving only a weak bound to growth; I couldn't prove $O(1)$ bound myself. Another paper on the subject: http://128.208.128.142/~ejpecp/ECP/include/getdoc.php?id=5086&article=2110&mode=pdf2011-12-06
  • 1
    Finding and then proving this (the expected value of a random assignment problem) was an outstanding research problem for over 30 years. It was not until the paper by Aldous appeared (the one mentioned by Srivatsan) that the problem was definitely settled. Hence the "it is normal that you do not understand why" in Goeman's notes. Variations, extensions, and simplifications of Aldous's result have since been proved, though. I blogged about this and some related problems [here](http://mikespivey.wordpress.com/2011/10/14/random-assignment-problems/).2011-12-06

1 Answers 1

1

Empirically using R

require(clue)
n <- 200 
m <- matrix(runif(n^2), ncol=n) 
s <- solve_LSAP(m) 
sum(m[cbind(seq_along(s), s)])

produces results of about 1.6.

Putting David J. Aldous, The zeta(2) limit in the random assignment problem [noted by Srivatsan] and the comment in conjecture 4 of Don Coppersmith and Gregory B. Sorkin, Constructive bounds and exact expectations for the random assignment problem [where this is conjecture 3] the result is $\pi^2/6 \approx 1.6449$. Both are worth reading.

This may not be a total surprise given that the lowest cost edge is likely to be less than $1/n^2$. On the other hand, it is not difficult to find the same limit for the wrong reasons.

  • 0
    Interesting, I'm reading the paper now.2011-12-06