On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension

DOI10.1287/MOOR.22.3.545MaRDI QIDQ4361783zbMATH OpenOpenAlexFDO

Authors Martin Dyer, R. Kannan

Publication date 28 October 1997

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/5f70ab3f7ea66111ab7cc9238a400bde2882f754

zbMATH Keywords

polynomial-time algorithm

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A Primal Barvinok Algorithm Based on Irrational Decompositions
• Effective lattice point counting in rational convex polytopes
• The many aspects of counting lattice points in polytopes

Cited in

(25)

• Computing the Ehrhart polynomial of a convex lattice polytope
• Integer programming, Barvinok's counting algorithm and Gomory relaxations.
• On the mean square of the remainder for the Euclidean lattice point counting problem
• Computing with an algebraic-perturbation variant of Barvinok's algorithm
• On the complexity of computing Kronecker coefficients
• Polyhedral circuits and their applications
• Counting lattice points on bargraphs of Catalan words
• On lattice point counting in -modular polyhedra
• Enumeration of integer points in projections of unbounded polyhedra
• The many aspects of counting lattice points in polytopes
• A computational study of integer programming algorithms based on Barvinok's rational functions
• Counting lattice vectors
• Effective lattice point counting in rational convex polytopes
• An algebraic-perturbation variant of Barvinok's algorithm
• Bias expansion of spatial statistics and approximation of differenced lattice point counts
• Enumerating projections of integer points in unbounded polyhedra
• A Primal Barvinok Algorithm Based on Irrational Decompositions
• An Alternative Algorithm for Counting Lattice Points in a Convex Polytope
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• Enumeration and unimodular equivalence of empty delta-modular simplices
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• A new and faster representation for counting integer points in parametric polyhedra
• Non-standard approaches to integer programming
• An algebraic combinatorial approach to Sylvester's denumerant
• Column basis reduction and decomposable knapsack problems

This page was built for publication: On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4361783)