Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Parametric polyhedra with at least k lattice points: their semigroup structure and the k-Frobenius problem

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)

Full text not available from this repository.


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

Actions (repository staff only)

Edit Item Edit Item