{
  "id": "1409.5259",
  "version": "v1",
  "published": "2014-09-18T11:09:32.000Z",
  "updated": "2014-09-18T11:09:32.000Z",
  "title": "Semigroups of Polyhedra with Prescribed Number of Lattice Points and the k-Frobenius Problem",
  "authors": [
    "Iskander Aliev",
    "Jesus A. De Loera",
    "Quentin Louveaux"
  ],
  "categories": [
    "math.CO",
    "math.NT",
    "math.OC"
  ],
  "abstract": "The well-studied semigroup sg(A)={b: b=Ax, x non-negative integral vector} can be stratified by the sizes of the polyhedral fibers IP_A(b)={x: Ax=b, x non-negative integral vector}. The key theme of this paper is a structure theory that characterizes precisely the set sg_{\\ge k}(A) of all vectors b in sg(A) such that their fiber IP_A(b) has at least k solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors b for which IP_A(b) has exactly k solutions or fewer than k solutions. The main result of this paper shows that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of sg_{\\ge k}(A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have at least k solutions. Using this tool we prove that for fixed n,k the k-Frobenius number can be computed in polynomial time, generalizing a well-known result of R. Kannan.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-18T11:09:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C07",
      "11D07",
      "05E40",
      "05A15"
    ],
    "keywords": [
      "lattice points",
      "k-frobenius problem",
      "prescribed number",
      "non-negative integral vector",
      "polynomial time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.5259A"
    }
  }
}