Aliev, Iskander, De Loera, Jesus and Louveaux, Quentin 2016. Parametric polyhedra with at least k lattice points: their semigroup structure and the k-Frobenius problem. In: Beveridge, A., Griggs, J. R., Hogben, L., Musiker, G. and Tetali, P. eds. Recent Trends in Combinatorics, The IMA Volumes in Mathematics and its Applications, Springer, pp. 753-778. (10.1007/978-3-319-24298-9_29) |
Abstract
Given an integral d×n matrix A, the well-studied affine semigroup Sg(A)={b:Ax=b, x∈Zn,x≥0} can be stratified by the number of lattice points inside the parametric polyhedra PA(b)={x:Ax=b,x≥0}. Such families of parametric polyhedra appear in many areas of combinatorics, convex geometry, algebra and number theory. The key themes of this paper are: (1) A structure theory that characterizes precisely the subset Sg≥k(A) of all vectors b∈ Sg(A) such that PA(b)∩Zn has at least k solutions. We demonstrate that this set is finitely generated, it is 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 PA(b)∩Zn has exactly k solutions or fewer than k solutions. (2) A computational complexity theory. We show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of Sg≥k(A) as a multivariate generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors of bounded norm that have at least k solutions. (3) Applications and computation for the k-Frobenius numbers. Using Generating functions we prove that for fixed n,k the k-Frobenius number can be computed in polynomial time. This generalizes a well-known result for k=1 by R. Kannan. Using some adaptation of dynamic programming we show some practical computations of k-Frobenius numbers and their relatives.
Item Type: | Book Section |
---|---|
Date Type: | Publication |
Status: | Published |
Schools: | Mathematics |
Subjects: | Q Science > QA Mathematics |
Publisher: | Springer |
ISBN: | 9783319242965 |
Related URLs: | |
Last Modified: | 24 Dec 2018 21:05 |
URI: | http://orca.cf.ac.uk/id/eprint/87675 |
Actions (repository staff only)
Edit Item |