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

1 November 1994

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research

Vol. 19 (4), 769-779
https://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.

Keywords

EUCLIDEAN
COUNTING INTEGRAL POINTS
ALGORITHM FOR COUNTING
POINTS IN POLYHEDRA
POLYNOMIAL TIME ALGORITHM

Cited by 206 articles