{
  "id": "2110.09901",
  "version": "v3",
  "published": "2021-10-17T17:50:38.000Z",
  "updated": "2023-10-05T19:46:44.000Z",
  "title": "A FPTAS for the Subset Sum Problem with Real Numbers",
  "authors": [
    "Marius Costandin"
  ],
  "comment": "It relies on maximizing the distance over an intersection of balls to a given point. The used algorithm for this however, is not able to solve the class of problem the SSP generates",
  "categories": [
    "math.OC"
  ],
  "abstract": "In this paper we study the subset sum problem with real numbers. Starting from the given problem, we formulate a quadratic maximization problem over a polytope which is eventually written as a distance maximization to a fixed point. For solving this, we provide a polynomial algorithm which maximizes the distance to a fixed point over a certain convex set. This convex set is obtained by intersecting the unit hypercube with two relevant half spaces. We show that in case the subset sum problem has a solution, our algorithm gives the correct maximum distance up to an arbitrary chosen precision. In such a case, we show that the obtained maximizer is a solution to the subset sum problem. Therefore, we compute the maximizer and upon analyzing it we can assert the feasibility of the subset sum problem.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2023-10-05T19:46:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "subset sum problem",
      "real numbers",
      "convex set",
      "arbitrary chosen precision",
      "fixed point"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}