A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. (English) Zbl 0821.90085

Barvinok, Alexander I.

Math. Oper. Res. 19, No. 4, 769-779 (1994).

Summary: 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.

MSC:

90C10	Integer programming
90C60	Abstract computational complexity for mathematical programming problems
52B12	Special polytopes (linear programming, centrally symmetric, etc.)
52C07	Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
52B55	Computational aspects related to convexity

Keywords:

polynomial time algorithm; counting integral points in polyhedra