Short rational generating functions for lattice point problems

DOI10.1090/S0894-0347-03-00428-4zbMath1017.05008arXivmath/0211146MaRDI QIDQ4419572

Kevin M. Woods, Alexander I. Barvinok

Publication date: 13 August 2003

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0211146

zbMATH Keywords

computational complexity generating functions semigroup Frobenius problem Hilbert series Hilbert basis

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Exact enumeration problems, generating functions (05A15) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Lattice points in specified regions (11P21)

Related Items

Polyhedral omega: a new algorithm for solving linear Diophantine systems, Optimizing Sparsity over Lattices and Semigroups, Counting essential surfaces in \(3\)-manifolds, On Dedekind's problem for complete simple games, Small Chvátal rank, Short rational functions for toric algebra and applications, Effective lattice point counting in rational convex polytopes, A Framework for Computing Zeta Functions of Groups, Algebras, and Modules, Short Presburger Arithmetic Is Hard, On lattice point counting in \(\varDelta\)-modular polyhedra, Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials, Algorithms for lattice games, Short rational generating functions for solving some families of fuzzy integer programming problems, Separator-based data reduction for signed graph balancing, The Computational Complexity of Integer Programming with Alternations, Parametric Presburger arithmetic: complexity of counting and quantifier elimination, Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints, Enumeration and unimodular equivalence of empty delta-modular simplices, Frobenius vectors, Hilbert series and gluings of affine semigroups., A mathematical programming approach to the computation of the omega invariant of a numerical semigroup, Khovanskii's theorem and effective results on sumset structure, Alternatives for testing total dual integrality, Graded local cohomology of modules over semigroup rings, The generalized Frobenius problem via restricted partition functions, A generalization of the integer linear infeasibility problem, Lattice games without rational strategies, An enumeration algorithm for all integers nonrepresentable by some positive integers, On the number of integer points in translated and expanded polyhedra, Algorithms for graded injective resolutions and local cohomology over semigroup rings, Computing local zeta functions of groups, algebras, and modules, Computing the integer programming gap, Enumerating Projections of Integer Points in Unbounded Polyhedra, Frobenius problem for semigroups \(\mathbf S(d_1,d_2,d_3)\)., Counting with rational generating functions, A new complexity result on multiobjective linear integer programming using short rational generating functions, Lattice point methods for combinatorial games, The many aspects of counting lattice points in polytopes, Parametric integer programming algorithm for bilevel mixed integer programs, New strings for old Veneziano amplitudes. III: Symplectic treatment, Rational polyhedral outer-approximations of the second-order cone, Frobenius Coin-Exchange Generating Functions, Computing the Ehrhart quasi-polynomial of a rational simplex, Analytic representations in the three-dimensional Frobenius problem, COUNTING NUMERICAL SEMIGROUPS WITH SHORT GENERATING FUNCTIONS, Ehrhart polynomials of matroid polytopes and polymatroids, COMPLEXITY OF SHORT GENERATING FUNCTIONS, A computational study of integer programming algorithms based on Barvinok's rational functions, Matrix computations with the Omega calculus, Sparse representation of vectors in lattices and semigroups

Uses Software

LattE

Cites Work