Enumerating projections of integer points in unbounded polyhedra
From MaRDI portal
Publication:4638995
DOI10.1137/17M1118907zbMATH Open1385.05017arXiv1612.08030OpenAlexW2796414002MaRDI QIDQ4638995FDOQ4638995
Authors: Danny Nguyen, Igor Pak 
Publication date: 2 May 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: We extend the Barvinok-Woods algorithm for enumerating projections of integer points in polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections of semilinear subsets of the integer lattice. We extend the results to general formulas in Presburger Arithmetic. We also give an application to the k-Frobenius problem.
Full work available at URL: https://arxiv.org/abs/1612.08030
Recommendations
- Enumeration of integer points in projections of unbounded polyhedra
- Short rational generating functions for lattice point problems
- Enumerating integer points in polytopes with bounded subdeterminants
- Computing with an algebraic-perturbation variant of Barvinok's algorithm
- On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
Symbolic computation and algebraic computation (68W30) Exact enumeration problems, generating functions (05A15) Lattice points in specified regions (11P21)
Cites Work
- Effective lattice point counting in rational convex polytopes
- Title not available (Why is that?)
- Integer Programming with a Fixed Number of Variables
- Bounded Algol-Like Languages
- On Context-Free Languages
- Parametric integer programming in fixed dimension
- Fast integer programming in fixed dimension
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- An application of simultaneous diophantine approximation in combinatorial optimization
- Title not available (Why is that?)
- Integer points in polyhedra
- Lattice translates of a polytope and the Frobenius problem
- Local Euler-Maclaurin formula for polytopes
- Title not available (Why is that?)
- On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
- Point location in arrangements of hyperplanes
- Computing the integer programming gap
- Short rational generating functions for lattice point problems
- A Primal Barvinok Algorithm Based on Irrational Decompositions
- Counting integer points in parametric polytopes using Barvinok's rational functions
- Computing parametric rational generating functions with a primal Barvinok algorithm
- Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
- Title not available (Why is that?)
- Complexity of Presburger arithmetic with fixed quantifier dimension
- A Polyhedral Frobenius Theorem with Applications to Integer Optimization
- Parametric polyhedra with at least \(k\) lattice points: their semigroup structure and the \(k\)-Frobenius problem
- The taming of the semi-linear set
- Complexity of short Presburger arithmetic
Cited In (7)
- Enumerating Collinear Points in Higher Dimensions
- Branching numbers for Euclidean projections onto convex polyhedra
- Enumeration of integer points in projections of unbounded polyhedra
- Enumerating a subset of the integer points inside a Minkowski sum
- Counting essential surfaces in \(3\)-manifolds
- Geometric decision procedures and the VC dimension of linear arithmetic theories
- Enumeration of Concrete Regular Covering Projections
Uses Software
This page was built for publication: Enumerating projections of integer points in unbounded polyhedra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638995)
