{
  "id": "1501.01944",
  "version": "v1",
  "published": "2015-01-08T20:15:00.000Z",
  "updated": "2015-01-08T20:15:00.000Z",
  "title": "Separating subadditive Euclidean functionals",
  "authors": [
    "Alan Frieze",
    "Wesley Pegden"
  ],
  "comment": "19 pages, 3 figures",
  "categories": [
    "math.PR",
    "cs.DM"
  ],
  "abstract": "If we are given $n$ random points in the hypercube $[0,1]^d$, then the minimum length of a Traveling Salesperson Tour through the points, the minimum length of a spanning tree, and the minimum length of a matching, etc., are known to be asymptotically $\\beta n^{\\frac{d-1}{d}}$ a.s., where $\\beta$ is an absolute constant in each case. We prove separation results for these constants. In particular, concerning the constants $\\beta_{\\mathrm{TSP}}^d$, $\\beta_{\\mathrm{MST}}^d$, $\\beta_{\\mathrm{MM}}^d$, and $\\beta_{\\mathrm{TF}}^d$ from the asymptotic formulas for the minimum length TSP, spanning tree, matching, and 2-factor, respectively, we prove that $\\beta_{\\mathrm{MST}}^d<\\beta_{\\mathrm{TSP}}^d$, $2\\beta_{\\mathrm{MM}}^d<\\beta_{\\mathrm{TSP}}^d$, and $\\beta_{\\mathrm{TF}}^d<\\beta_{\\mathrm{TSP}}^d$ for all $d\\geq 2$. Our results have some computational relevance, showing that a certain natural class of simple algorithms cannot solve the random Euclidean TSP efficiently.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-01-08T20:15:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05"
    ],
    "keywords": [
      "separating subadditive euclidean functionals",
      "spanning tree",
      "minimum length tsp",
      "absolute constant",
      "random euclidean tsp"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}