Enumerating Projections of Integer Points in Unbounded Polyhedra

DOI10.1137/17M1118907zbMath1385.05017arXiv1612.08030OpenAlexW2796414002MaRDI QIDQ4638995

Igor Pak, Danny Nguyen

Publication date: 2 May 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

generating functionspolyhedraprojectioncountingpolynomial timeinteger points

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Exact enumeration problems, generating functions (05A15) Lattice points in specified regions (11P21)

Related Items

Counting essential surfaces in \(3\)-manifolds

Uses Software

• LattE
• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Point location in arrangements of hyperplanes
• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
• Integer points in polyhedra
• Counting integer points in parametric polytopes using Barvinok's rational functions
• Computing parametric rational generating functions with a primal Barvinok algorithm
• An application of simultaneous diophantine approximation in combinatorial optimization
• Lattice translates of a polytope and the Frobenius problem
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Computing the integer programming gap
• Effective lattice point counting in rational convex polytopes
• Parametric polyhedra with at least k lattice points: Their semigroup structure and the k-Frobenius problem
• Integer Programming with a Fixed Number of Variables
• Parametric Integer Programming in Fixed Dimension
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• Short rational generating functions for lattice point problems
• The taming of the semi-linear set
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Complexity of short Presburger arithmetic
• Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials
• A Primal Barvinok Algorithm Based on Irrational Decompositions
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• Bounded Algol-Like Languages
• On Context-Free Languages
• Algorithms - ESA 2003