A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed

Alexander I. Barvinok
Alexander I. Barvinok
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1003
Search for more papers by this author

Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1003

Published Online:1 Nov 1994https://doi.org/10.1287/moor.19.4.769

Abstract

We prove that for any dimension d there exists a polynomial time algorithm for counting integral points in polyhedra in the d-dimensional Euclidean space. Previously such algorithms were known for dimensions d = 1, 2, 3, and 4 only.

Cited by
- Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
  18 December 2025 | computational complexity, Vol. 35, No. 1
- Payment Splitting in Lightning Network as a Mitigation Against Balance Discovery Attacks
  Blockchain: Research and Applications, Vol. 12059
- A combinatorial algorithm to compute the triangular convex skull of a digital object
  9 February 2026 | Multimedia Tools and Applications, Vol. 85, No. 2
- A degenerate version of Brion's formula
  Advances in Mathematics, Vol. 486
- External Columns and Chambers of Vector Partition Functions
  3 November 2025 | Discrete & Computational Geometry, Vol. 75, No. 1
- Towards efficient program execution on edge-cloud computing platforms
  Journal of Parallel and Distributed Computing, Vol. 205
- The nonlinear algebra view of discrete mathematics
- Fast evaluation of generalized Todd polynomials: Applications to MacMahon's partition analysis and integer programming
  Journal of Symbolic Computation, Vol. 130
- Integer Hulls, Z-Polyhedra and Presburger Arithmetic in Action
  20 January 2026 | ACM Communications in Computer Algebra, Vol. 59, No. 3
- Quantifier Elimination Over the Integers
  10 November 2025
- A Polynomial Time Algorithm for Calculating Fourier-Dedekind Sums
  19 June 2024 | Experimental Mathematics, Vol. 34, No. 3
- Finite integrals from Feynman polytopes
  14 May 2025 | Physical Review D, Vol. 111, No. 10
- Accounting for Missing Events in Statistical Information Leakage Analysis
- An algebraic combinatorial approach to Sylvester’s denumerant
  12 February 2025 | The Ramanujan Journal, Vol. 66, No. 4
- Distributed-Optimization With Centralized-Refining for Efficient Resource Allocation in Future Wireless Networks
  IEEE Transactions on Communications, Vol. 72, No. 8
- Linear-time uniform generation of random sparse contingency tables with specified marginals
  The Annals of Applied Probability, Vol. 34, No. 2
- Counting the Integer Points of Parametric Polytopes: A Maple Implementation
  21 August 2024
- Quantitative Symbolic Robustness Verification for Quantized Neural Networks
  29 November 2024
- What is a combinatorial interpretation?
- Improved estimates for the number of non-negative integer matrices with given row and column sums
  24 January 2024 | Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, Vol. 480, No. 2282
- Experimental Statistics for Mirzakhani’s Theorem
  16 October 2021 | Experimental Mathematics, Vol. 32, No. 4
- A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
  Operations Research Letters, Vol. 51, No. 5
- Autotuning Convolutions Is Easier Than You Think
  1 March 2023 | ACM Transactions on Architecture and Code Optimization, Vol. 20, No. 2
- Obtaining Information Leakage Bounds via Approximate Model Counting
  6 June 2023 | Proceedings of the ACM on Programming Languages, Vol. 7, No. PLDI
- PopArt: Ranked Testing Efficiency
  IEEE Transactions on Software Engineering, Vol. 49, No. 4
- BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation
  17 November 2022 | ACM Transactions on Architecture and Code Optimization, Vol. 20, No. 1
- Contingent Capital with Stock Price Triggers in Interbank Networks
  Anne G. Balter,
  Nikolaus Schweizer,
  Juan C. Vera
  11 August 2022 | Mathematics of Operations Research, Vol. 48, No. 1
- Exact algorithms for multiobjective linear optimization problems with integer variables: A state of the art survey
  10 March 2022 | Journal of Multi-Criteria Decision Analysis, Vol. 29, No. 5-6
- How to find the convex hull of all integer points in a polyhedron?
  15 April 2021 | Optimization Letters, Vol. 16, No. 7
- On lattice point counting in $$\varDelta $$-modular polyhedra
  25 May 2021 | Optimization Letters, Vol. 16, No. 7
- Computing Optimized Path Integrals for Knapsack Feasibility
  Endric Daues,
  Ulf Friedrich,
  15 February 2022 | INFORMS Journal on Computing, Vol. 34, No. 4
- Approximating sums by integrals only: multiple sums and sums over lattice polytopes
  15 June 2022 | Constructive Mathematical Analysis, Vol. 5, No. 2
- Counting essential surfaces in 3-manifolds
  25 January 2022 | Inventiones mathematicae, Vol. 228, No. 2
- Inconsistent weighting in weighted voting games
  25 January 2022 | Public Choice, Vol. 191, No. 1-2
- Majority properties of positional social preference correspondences
  15 June 2021 | Theory and Decision, Vol. 92, No. 2
- Enumerating Integer Points in Polytopes with Bounded Subdeterminants
  14 February 2022 | SIAM Journal on Discrete Mathematics, Vol. 36, No. 1
- Quantifier elimination for counting extensions of Presburger arithmetic
  29 March 2022
- Computing the Integer Hull of Convex Polyhedral Sets
  11 August 2022
- IOOpt: automatic derivation of I/O complexity bounds for affine programs
  18 June 2021
- Rational polyhedral outer-approximations of the second-order cone
  Discrete Optimization, Vol. 40
- Dummy Players and the Quota in Weighted Voting Games
  21 September 2020 | Group Decision and Negotiation, Vol. 30, No. 1
- IAC Probability Calculations in Voting Theory: Progress Report
  19 December 2020
- Analyzing the Practical Relevance of the Condorcet Loser Paradox and the Agenda Contraction Paradox
  19 December 2020
- On the Pseudo-Periodicity of the Integer Hull of Parametric Convex Polygons
  16 August 2021
- ALONA: Automatic Loop Nest Approximation with Reconstruction and Space Pruning
  25 August 2021
- Reduced Products of Abstract Domains for Fairness Certification of Neural Networks
  13 October 2021
- Perfectly parallel fairness certification of neural networks
  13 November 2020 | Proceedings of the ACM on Programming Languages, Vol. 4, No. OOPSLA
- A mechanism for balancing accuracy and scope in cross-machine black-box GPU performance modeling
  3 June 2020 | The International Journal of High Performance Computing Applications, Vol. 34, No. 6
- Symbolic Execution + Model Counting + Entropy Maximization = Automatic Search Synthesis
  20 September 2020 | Electronic Proceedings in Theoretical Computer Science, Vol. 326
- Automated derivation of parametric data movement lower bounds for affine programs
  11 June 2020
- Efficiently Testing Digital Convexity and Recognizing Digital Convex Polygons
  11 May 2020 | Journal of Mathematical Imaging and Vision, Vol. 62, No. 5
- PASAPTO: Policy-aware Security and Performance Trade-off Analysis--Computation on Encrypted Data with Restricted Leakage
- Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration
  Hiroshi Hirai,
  Ryunosuke Oshiro,
  Ken’ichiro Tanaka
  27 November 2019 | Mathematics of Operations Research, Vol. 45, No. 2
- Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
  Dimitris Bertsimas,
  Bradley Sturt
  30 April 2020 | Operations Research, Vol. 68, No. 3
- Probabilities of electoral outcomes: from three-candidate to four-candidate elections
  21 October 2019 | Theory and Decision, Vol. 88, No. 2
- Local formulas for Ehrhart coefficients from lattice tiles
  15 June 2019 | Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, Vol. 61, No. 1
- The Z_Polyhedra Library in Maple
  28 February 2020
- Polyhedral Circuits and Their Applications
  9 August 2020
- MCBAT: Model Counting for Constraints over Bounded Integer Arrays
  6 December 2020
- Subformula Caching for Model Counting and Quantitative Program Analysis
- Parametric Presburger arithmetic: complexity of counting and quantifier elimination
  2 September 2019 | Mathematical Logic Quarterly, Vol. 65, No. 2
- Mixed-radix Naccache–Stern encryption
  17 March 2018 | Journal of Cryptographic Engineering, Vol. 9, No. 3
- Verifying and Quantifying Side-channel Resistance of Masked Software Implementations
  18 July 2019 | ACM Transactions on Software Engineering and Methodology, Vol. 28, No. 3
- Computing the integer points of a polyhedron
  30 May 2019 | ACM Communications in Computer Algebra, Vol. 52, No. 4
- Approximating the volume of tropical polytopes is difficult
  2 April 2019 | International Journal of Algebra and Computation, Vol. 29, No. 02
- Disjunctive Relational Abstract Interpretation for Interprocedural Program Analysis
  11 January 2019
- Efficient Algorithms to Test Digital Convexity
  23 February 2019
- Location Problems with Multiple Criteria
  17 March 2020
- Reachability Analysis of Low‐Order Discrete State Reaction Networks Obeying Conservation Laws
  26 March 2019 | Complexity, Vol. 2019, No. 1
- Three Ehrhart quasi-polynomials
  6 June 2019 | Algebraic Combinatorics, Vol. 2, No. 3
- Speeding up Iterative Polyhedral Schedule Optimization with Surrogate Performance Models
  19 December 2018 | ACM Transactions on Architecture and Code Optimization, Vol. 15, No. 4
- Locality analysis through static parallel sampling
  11 June 2018 | ACM SIGPLAN Notices, Vol. 53, No. 4
- On approximation algorithms for concave mixed-integer quadratic programming
  25 July 2017 | Mathematical Programming, Vol. 172, No. 1-2
- Parameterized model counting for string and numeric constraints
  26 October 2018
- Computing weight q-multiplicities for the representations of the simple Lie algebras
  1 November 2017 | Applicable Algebra in Engineering, Communication and Computing, Vol. 29, No. 4
- A survival guide to presburger arithmetic
  26 July 2018 | ACM SIGLOG News, Vol. 5, No. 3
- Analytic Combinatorics and Labeling in High Level Fusion and Multihypothesis Tracking
- Locality analysis through static parallel sampling
  11 June 2018
- Computing with an algebraic-perturbation variant of Barvinok’s algorithm
  Discrete Applied Mathematics, Vol. 240
- Online Synthesis of Adaptive Side-Channel Attacks Based On Noisy Observations
- Ehrhart tensor polynomials
  Linear Algebra and its Applications, Vol. 539
- The polyhedra library in m aple
  4 January 2018 | ACM Communications in Computer Algebra, Vol. 51, No. 3
- SCInfer: Refinement-Based Verification of Software Countermeasures Against Side-Channel Attacks
  18 July 2018
- Volume-Based Merge Heuristics for Disjunctive Numeric Domains
  29 August 2018
- The many aspects of counting lattice points in polytopes
  22 September 2017
- Monotonicity paradoxes in three-candidate elections using scoring elimination rules
  26 June 2017 | Social Choice and Welfare, Vol. 50, No. 1
- Computation of dilated Kronecker coefficients
  Journal of Symbolic Computation, Vol. 84
- Enumerating Projections of Integer Points in Unbounded Polyhedra
  SIAM Journal on Discrete Mathematics, Vol. 32, No. 2
- A polynomial algorithm for packing unit squares in a hypograph of a piecewise linear function
  Open Engineering, Vol. 7, No. 1
- Fourier Transform of a Polytope and its Applications in Geometric Combinatorics
- Asymptotic vulnerability of positional voting rules to coalitional manipulation
  Mathematical Social Sciences, Vol. 89
- Scoring Rules and Preference Restrictions: The Strong Borda Paradox Revisited
  Revue d'économie politique, Vol. Vol. 127, No. 3
- Scoring Rules and Preference Restrictions: The Strong Borda Paradox Revisited
  Revue d'économie politique, Vol. Vol. 127, No. 3
- Polyhedral Omega: a New Algorithm for Solving Linear Diophantine Systems
  26 April 2017 | Annals of Combinatorics, Vol. 21, No. 2
- Stable Rules for Electing Committees and Divergence on Outcomes
  27 July 2016 | Group Decision and Negotiation, Vol. 26, No. 3
- Computing convex hulls and counting integer points with polymake
  23 May 2016 | Mathematical Programming Computation, Vol. 9, No. 1
- Integral points in rational polygons: a numerical semigroup approach
  2 September 2016 | Semigroup Forum, Vol. 94, No. 1
- Sampling for Conditional Inference on Contingency Tables
  16 February 2017 | Journal of Computational and Graphical Statistics, Vol. 26, No. 1
- Probabilistic Program Analysis
  29 June 2017
- Computing the Integer Points of a Polyhedron, I: Algorithm
  30 August 2017
- The width and integer optimization on simplices with bounded minors of the constraint matrices
  13 June 2016 | Optimization Letters, Vol. 10, No. 6
- Codes for DNA Sequence Profiles
  IEEE Transactions on Information Theory, Vol. 62, No. 6
- Correlation, partitioning and the probability of casting a decisive vote under the majority rule
  Journal of Mathematical Economics, Vol. 64
- Parametric polyhedra with at least k lattice points: Their semigroup structure and the k-Frobenius problem
  13 April 2016
- Computing points of bounded height in projective space over a number field
  9 June 2015 | Mathematics of Computation, Vol. 85, No. 297
- An algebraic-perturbation variant of Barvinok's algorithm
  Electronic Notes in Discrete Mathematics, Vol. 50
- A fixed point iterative approach to integer programming and its distributed computation
  6 October 2015 | Fixed Point Theory and Applications, Vol. 2015, No. 1
- Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases
  25 June 2014 | Annals of the Institute of Statistical Mathematics, Vol. 67, No. 4
- Short rational generating functions for solving some families of fuzzy integer programming problems
  Fuzzy Sets and Systems, Vol. 272
- Array Interleaving—An Energy-Efficient Data Layout Transformation
  24 June 2015 | ACM Transactions on Design Automation of Electronic Systems, Vol. 20, No. 3
- PRESBURGER ARITHMETIC, RATIONAL GENERATING FUNCTIONS, AND QUASI-POLYNOMIALS
  22 April 2015 | The Journal of Symbolic Logic, Vol. 80, No. 2
- Codes for DNA sequence profiles
- A Euclid style algorithm for MacMahon's partition analysis
  Journal of Combinatorial Theory, Series A, Vol. 131
- Codes for DNA storage channels
- The Coin-Exchange Problem of Frobenius
- h-Polynomials and h ∗-Polynomials
- The Decomposition of a Polytope into Its Cones
- Euler–Maclaurin Summation in ℝd
- Solid Angles
- A Discrete Version of Green’s Theorem Using Elliptic Functions
- A Gallery of Discrete Volumes
- Counting Lattice Points in Polytopes: The Ehrhart Theory
- Reciprocity
- Face Numbers and the Dehn–Sommerville Relations in Ehrhartian Terms
- Magic Squares
- Finite Fourier Analysis
- Dedekind Sums, the Building Blocks of Lattice-Point Enumeration
- Zonotopes
- Location Problems with Multiple Criteria
  21 January 2015
- An Invitation to Ehrhart Theory: Polyhedral Geometry and its Applications in Enumerative Combinatorics
  21 January 2015
- Symbolic Polytopes for Quantitative Interpolation and Verification
  16 July 2015
- Model Counting for Complex Data Structures
  27 August 2015
- Eigenvalue Distributions of Reduced Density Matrices
  19 August 2014 | Communications in Mathematical Physics, Vol. 332, No. 1
- A Randomized Sieving Algorithm for Approximate Integer Programming
  20 September 2013 | Algorithmica, Vol. 70, No. 2
- Satisfiability modulo counting
  14 July 2014
- Automatic complexity analysis of explicitly parallel programs
  21 June 2014
- Abstract model counting
  4 June 2014
- Precise quantitative information flow analysis— a symbolic approach
  Theoretical Computer Science, Vol. 538
- An algorithm for the separation of two-row cuts
  11 October 2012 | Mathematical Programming, Vol. 143, No. 1-2
- Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem
- Getting Started
  26 September 2014
- Semidefinite Bounds
  26 September 2014
- Linear Inequalities and Polyhedra
  26 September 2014
- Valid Inequalities for Structured Integer Programs
  26 September 2014
- Reformulations and Relaxations
  26 September 2014
- Enumeration
  26 September 2014
- Combinatorics and geometry of transportation polytopes: An update
- Cohomology for Frobenius kernels of SL2
  Journal of Algebra, Vol. 396
- Exact sampling and counting for fixed-margin matrices
  The Annals of Statistics, Vol. 41, No. 3
- On Dedekind’s problem for complete simple games
  7 April 2012 | International Journal of Game Theory, Vol. 42, No. 2
- Exploiting polyhedral symmetries in social choice
  13 April 2012 | Social Choice and Welfare, Vol. 40, No. 4
- On the bit-complexity of sparse polynomial and series multiplication
  Journal of Symbolic Computation, Vol. 50
- Exploiting Symmetries in Polyhedral Computations
  17 May 2013
- Automation of Quantitative Information-Flow Analysis
- Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials
- INTERMEDIATE SUMS ON POLYHEDRA: COMPUTATION AND REAL EHRHART THEORY
  5 September 2012 | Mathematika, Vol. 59, No. 1
- Foundations of Discrete Optimization: In Transition from Linear to Non-linear Models and Methods
  13 December 2012 | Jahresbericht der Deutschen Mathematiker-Vereinigung, Vol. 114, No. 4
- Symbolic quantitative information flow
  27 November 2012 | ACM SIGSOFT Software Engineering Notes, Vol. 37, No. 6
- Computing Multiplicities of Lie Group Representations
- Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra
  12 November 2011 | Foundations of Computational Mathematics, Vol. 12, No. 4
- An example of probability computations under the IAC assumption: The stability of scoring rules
  Mathematical Social Sciences, Vol. 64, No. 1
- Counting Contingency Tables via Multistage Markov Chain Monte Carlo
  Journal of Computational and Graphical Statistics, Vol. 21, No. 3
- Minkowski Length of 3D Lattice Polytopes
  28 June 2012 | Discrete & Computational Geometry, Vol. 19
- Sum-integral interpolators and the Euler-Maclaurin formula for polytopes
  14 February 2012 | Transactions of the American Mathematical Society, Vol. 364, No. 6
- Integer affine transformations of parametric ℤ-polytopes and applications to loop nest optimization
  15 June 2012 | ACM Transactions on Architecture and Code Optimization, Vol. 9, No. 2
- A new complexity result on multiobjective linear integer programming using short rational generating functions
  1 February 2011 | Optimization Letters, Vol. 6, No. 3
- On the Complexity of Nonlinear Mixed-Integer Optimization
  15 November 2011
- A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming
- Quasi-polynomials, linear Diophantine equations and semi-linear sets
  Theoretical Computer Science, Vol. 416
- Rational Generating Functions and Integer Programming Games
  Matthias Köppe,
  Christopher Thomas Ryan,
  Maurice Queyranne,
  1 December 2011 | Operations Research, Vol. 59, No. 6
- COUNTING NUMERICAL SEMIGROUPS WITH SHORT GENERATING FUNCTIONS
  5 April 2012 | International Journal of Algebra and Computation, Vol. 21, No. 07
- Downlink SINR distribution in a heterogeneous cellular wireless network with max-SINR connectivity
- On the Occurrence Probability of Local Binary Patterns: A Theoretical Study
  1 February 2011 | Journal of Mathematical Imaging and Vision, Vol. 40, No. 3
- Bias expansion of spatial statistics and approximation of differenced lattice point counts
  27 May 2011 | Proceedings - Mathematical Sciences, Vol. 121, No. 2
- Experiments with the Site Frequency Spectrum
  23 December 2010 | Bulletin of Mathematical Biology, Vol. 73, No. 4
- Multivariate splines and polytopes
  Journal of Approximation Theory, Vol. 163, No. 3
- Lifting the Fundamental Cone and Enumerating the Pseudocodewords of a Parity-Check Code
  IEEE Transactions on Information Theory, Vol. 57, No. 2
- Basis Reduction Methods
  14 January 2011
- Integer Programming Duality
  15 February 2011
- Approximation and Randomization for Quantitative Information-Flow Analysis
- Computing pure strategy nash equilibria in compact symmetric games
  7 June 2010
- A mapping path for multi-GPGPU accelerated computers from a portable high level programming abstraction
  14 March 2010
- Integer Programming and Algorithmic Geometry of Numbers
  6 November 2009
- Nonlinear Integer Programming
  6 November 2009
- Approximately Counting Integral Flows and Cell-Bounded Contingency Tables
  SIAM Journal on Computing, Vol. 39, No. 7
- Staircases in
  Integers, Vol. 10, No. 6
- Ehrhart Polynomials of Matroid Polytopes and Polymatroids
  9 May 2008 | Discrete & Computational Geometry, Vol. 42, No. 4
- Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons
  13 August 2008 | Algorithmica, Vol. 55, No. 2
- Column basis reduction and decomposable knapsack problems
  Discrete Optimization, Vol. 6, No. 3
- Automatic Discovery and Quantification of Information Leaks
- Pareto Optima of Multicriteria Integer Linear Programs
  Jesús A. De Loera,
  Raymond Hemmecke,
  Matthias Köppe,
  5 September 2008 | INFORMS Journal on Computing, Vol. 21, No. 1
- Integer Polyhedra for Program Analysis
- The LLL Algorithm and Integer Programming
  7 October 2009
- (Formulas of Brion, Lawrence, and Varchenko on rational generating functions for cones)
  3 December 2008 | The Mathematical Intelligencer, Vol. 31, No. 1
- Counting Tables Using the Double-Saddlepoint Approximation
  Journal of Computational and Graphical Statistics, Vol. 18, No. 4
- Parametric Integer Programming in Fixed Dimension
  Friedrich Eisenbrand,
  Gennady Shmonin,
  10 October 2008 | Mathematics of Operations Research, Vol. 33, No. 4
- Storage Estimation and Design Space Exploration Methodologies for the Memory Management of Signal Processing Applications
  14 June 2008 | Journal of Signal Processing Systems, Vol. 53, No. 1-2
- FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
  1 September 2007 | Mathematical Programming, Vol. 115, No. 2
- Dedekind–Carlitz polynomials as lattice-point enumerators in rational polyhedra
  1 April 2008 | Mathematische Annalen, Vol. 341, No. 4
- A generalization of the integer linear infeasibility problem
  Discrete Optimization, Vol. 5, No. 1
- Counting with rational generating functions
  Journal of Symbolic Computation, Vol. 43, No. 2
- Counting Solutions of Integer Programs Using Unrestricted Subtree Detection
- A Closed Form Expression for the Number of Costas Arrays of Arbitrary Order
- Evaluation of storage requirements and applications in the memory management for multidimensional signal processing systems
- Computation of the Minimum Data Storage for Multi-Dimensional Signal Processing
- Computation of Storage Requirements for Multi-Dimensional Signal Processing Applications
  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 15, No. 4
- Order Statistics in the Farey Sequences in Sublinear Time
- A Primal Barvinok Algorithm Based on Irrational Decompositions
  SIAM Journal on Discrete Mathematics, Vol. 21, No. 1
- Computing the Ehrhart quasi-polynomial of a rational simplex
  10 March 2006 | Mathematics of Computation, Vol. 75, No. 255
- Integer Polynomial Optimization in Fixed Dimension
  Jesús A. De Loera,
  Raymond Hemmecke,
  Matthias Köppe,
  Robert Weismantel,
  1 February 2006 | Mathematics of Operations Research, Vol. 31, No. 1
- Loop Transformation Methodologies for Array-Oriented Memory Management
- Memory size computation for multimedia processing applications
- Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
  SIAM Journal on Computing, Vol. 36, No. 1
- Ehrhart Polynomials and Successive Minima
  1 December 2005 | Mathematika, Vol. 52, No. 1-2
- The many aspects of counting lattice points in polytopes
  Mathematische Semesterberichte, Vol. 52, No. 2
- A computational study of integer programming algorithms based on Barvinok's rational functions
  Discrete Optimization, Vol. 2, No. 2
- Approximately counting integral flows and cell-bounded contingency tables
  22 May 2005
- Ehrhart polynomials
- Integer Programming, Lattices, and Results in Fixed Dimension
- Effective lattice point counting in rational convex polytopes
  Journal of Symbolic Computation, Vol. 38, No. 4
- Short rational functions for toric algebra and applications
  Journal of Symbolic Computation, Vol. 38, No. 2
- Refined upper bounds for the linear Diophantine problem of Frobenius
  Advances in Applied Mathematics, Vol. 32, No. 3
- Integer programming, Barvinok's counting algorithm and Gomory relaxations
  Operations Research Letters, Vol. 32, No. 2
- An Automata-Theoretic Algorithm for Counting Solutions to Presburger Formulas
- Three Kinds of Integer Programming Algorithms Based on Barvinok’s Rational Functions
- Algebraic techniques in the memory size computation of multimedia processing applications
- The Complexity of Three-Way Statistical Tables
  SIAM Journal on Computing, Vol. 33, No. 4
- On Counting Integral Points in a Convex Rational Polytope
  Jean B. Lasserre,
  Eduardo S. Zeron,
  1 November 2003 | Mathematics of Operations Research, Vol. 28, No. 4
- Short rational generating functions for lattice point problems
  25 April 2003 | Journal of the American Mathematical Society, Vol. 16, No. 4
- A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
  Journal of Computer and System Sciences, Vol. 67, No. 2
- Evaluation of Dedekind sums, Eisenstein cocycles, and special values of L-functions
  Duke Mathematical Journal, Vol. 118, No. 2
- Non-standard approaches to integer programming
  Discrete Applied Mathematics, Vol. 123, No. 1-3
- Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows
- Values of zeta functions at negative integers, Dedekind sums and toric geometry
  18 September 2000 | Journal of the American Mathematical Society, Vol. 14, No. 1
- An Introduction to Empty Lattice Simplices
  30 April 1999
- On The Complexity of Computing Mixed Volumes
  SIAM Journal on Computing, Vol. 27, No. 2
- Barvinok's algorithm and the Todd class of a toric variety
  Journal of Pure and Applied Algebra, Vol. 117-118
- Computing integral points in convex semi-algebraic sets

cover image Mathematics of Operations Research

Volume 19, Issue 4

November 1994

Pages 769-1022

Article Information

Metrics

Information

Published Online:November 01, 1994

Cite as

Alexander I. Barvinok, (1994) A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Mathematics of Operations Research 19(4):769-779.

https://doi.org/10.1287/moor.19.4.769

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed

Abstract

Volume 19, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News