2012/07/04 by Friedrich Eisenbrand, Eisenbrand, Friedrich, Nicolai Hähnle +1
Computer Science · Mathematics · #11H06 #68Q25 #Advanced Combinatorial Mathematics #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #Number Theory (math.NT) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1207.0979
openalex publication_date 2012/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The parametric lattice-point counting problem is as follows: Given an integer matrix A ∈ Zm × n, compute an explicit formula parameterized by b ∈ Rm that determines the number of integer points in the polyhedron \x ∈ Rn : Ax ≤ b\. In the last decade, this counting problem has received considerable attention in the literature. Several variants of Barvinok's algorithm have been shown to solve this problem in polynomial time if the number n of columns of A is fixed. Central to our investigation is the following question: Can one also efficiently determine a parameter b such that the number of integer points in \x ∈ Rn : Ax ≤ b\ is minimized? Here, the parameter b can be chosen from a given polyhedron Q ⊆ Rm. Our main result is a proof that finding such a minimizing parameter is NP-hard, even in dimension 2 and even if the parametrization reflects a translation of a 2-dimensional convex polygon. This result is established via a relationship of this problem to arithmetic progressions and simultaneous Diophantine approximation. On the positive side we show that in dimension 2 there exists a polynomial time algorithm for each fixed k that either determines a minimizing translation or asserts that any translation contains at most 1 + 1/k times the minimal number of lattice points.