{
  "id": "2001.01078",
  "version": "v1",
  "published": "2020-01-04T13:31:49.000Z",
  "updated": "2020-01-04T13:31:49.000Z",
  "title": "On the Hardness of Almost All Subset Sum Problems by Ordinary Branch-and-Bound",
  "authors": [
    "Mustafa Kemal Tural"
  ],
  "comment": "5 pages",
  "journal": "Proceeding of the \"Uluslararasi Bilim, Teknoloji ve Sosyal Bilimlerde Guncel Gelismeler Sempozyumu\", 20-22 December 2019, Ankara, Turkey",
  "categories": [
    "math.OC",
    "cs.DM"
  ],
  "abstract": "Given $n$ positive integers $a_1,a_2,\\dots,a_n$, and a positive integer right hand side $\\beta$, we consider the feasibility version of the subset sum problem which is the problem of determining whether a subset of $a_1,a_2,\\dots,a_n$ adds up to $\\beta$. We show that if the right hand side $\\beta$ is chosen as $\\lfloor r\\sum_{j=1}^n a_j \\rfloor$ for a constant $0 < r < 1$ and if the $a_j$'s are independentand identically distributed from a discrete uniform distribution taking values ${1,2,\\dots,\\lfloor 10^{n/2} \\rfloor }$, then the probability that the instance of the subset sum problem generated requires the creation of an exponential number of branch-and-bound nodes when one branches on the individual variables in any order goes to $1$ as $n$ goes to infinity.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-01-04T13:31:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "G.2.1",
      "F.2.0",
      "G.2.1",
      "F.2.0"
    ],
    "keywords": [
      "subset sum problem",
      "ordinary branch-and-bound",
      "positive integer right hand side",
      "discrete uniform distribution",
      "individual variables"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}