{
  "id": "math/0004175",
  "version": "v2",
  "published": "2000-04-27T20:31:58.000Z",
  "updated": "2000-05-12T00:59:11.000Z",
  "title": "On the expected value of the minimum assignment",
  "authors": [
    "Marshall W. Buck",
    "Clara S. Chan",
    "David P. Robbins"
  ],
  "comment": "40 pages, New version updates reference, corrects typos, and contains minor improvements of some results",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The minimum k-assignment of an m by n matrix X is the minimum sum of k entries of X, no two of which belong to the same row or column. If X is generated by choosing each entry independently from the exponential distribution with mean 1, then Coppersmith and Sorkin conjectured that the expected value of its minimum k-assignment is \\sum_{i,j \\ge 0, i+j<k} 1/((m-i)(n-j)) and they (with Alm) have proven this for k < 5 and in certain cases when k=5 or k=6. They were motivated by the special case of k=m=n, where the expected value was conjectured by Parisi to be \\sum_{i=1}^k 1/(i^2). In this paper we describe our efforts to prove the Coppersmith-Sorkin conjecture. We give evidence for the following stronger conjecture, which generalizes theirs. Conjecture. Suppose that r_1,...,r_m and c_1,...,c_n are positive real numbers. Let X be a random m by n matrix in which entry x_{ij} is chosen independently from the exponential distribution with mean 1/(r_ic_j). Then the expected value of the minimum k-assignment of X is \\sum_{I,J} (-1)^{k - 1 - |I| - |J|} \\binom{m + n - 1 - |I| - |J|}{k - 1 - |I| - |J|}\\frac{1}{(\\sum_{i \\notin I}r_i) (\\sum_{j \\notin J} c_j)}. Here the sum is over proper subsets I of {1,...,m} and J of {1,...,n} whose cardinalities |I| and |J| satisfy |I|+|J|<k.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2000-05-12T00:59:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "expected value",
      "minimum assignment",
      "minimum k-assignment",
      "exponential distribution",
      "special case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 40,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2000math......4175B"
    }
  }
}