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?

$\endgroup$
7
  • 3
    $\begingroup$ This paper seems to be relevant: Aldous, Min, The $\zeta(2)$ Limit in the Random Assignment Problem (2000). $\endgroup$
    – Srivatsan
    Dec 6, 2011 at 0:46
  • $\begingroup$ 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. $\endgroup$
    – Henry
    Dec 6, 2011 at 0:46
  • $\begingroup$ 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}$. $\endgroup$
    – sdcvvc
    Dec 6, 2011 at 0:53
  • $\begingroup$ @Henry Sorry for that. Yes I mean the min cost instead of n. $\endgroup$
    – FiniteA
    Dec 6, 2011 at 1:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mike Spivey
    Dec 6, 2011 at 3:55

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting, I'm reading the paper now. $\endgroup$
    – FiniteA
    Dec 6, 2011 at 2:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .