{
  "id": "1504.00312",
  "version": "v1",
  "published": "2015-04-01T17:41:04.000Z",
  "updated": "2015-04-01T17:41:04.000Z",
  "title": "Minimum-cost matching in a regular bipartite graph with random costs",
  "authors": [
    "Alan Frieze",
    "Tony Johansson"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be an arbitrary $d$-regular bipartite graph on $2N$ vertices. Suppose that each edge $e$ is given an independent uniform exponential rate one cost. Let $C(G)$ denote the expected length of the minimum cost perfect matching. We show that if $d=d(N)\\to\\infty$ as $N\\to\\infty$, then $E(C(G)) =(1+o(1))\\frac{N}{d} \\frac{\\pi^2}{6}$. This generalises the well-known result for the case $G=K_{N,N}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-04-01T17:41:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "regular bipartite graph",
      "random costs",
      "minimum-cost matching",
      "independent uniform exponential rate",
      "well-known result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150400312F"
    }
  }
}