A Quantitative Doignon-Bell-Scarf Theorem

Abstract

The famous Doignon-Bell-Scarf Theorem is a Helly-type result about the existence of integer solutions on systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer $k$, we prove that there exists a constant $c(n,k)$, depending only on the dimension $n$ and $k$, such that if a polyhedron $x:Ax\le b$ contains exactly k integer solutions, then there exists a subset of the rows, of cardinality no more than $c(n,k)$, defining a polyhedron that contains exactly the same $k$ integer points. In this case $c(n,0)=2^n$ is the original case of Doignon-Bell-Scarf for infeasible systems of inequalities. We work on both upper and lower bounds for the constant $c(n,k)$ and discuss some consequences, including a Clarkson-style algorithm to find the $l$-th best solution of an integer program with respect to the ordering induced by the objective function.

Cited by in corpus (7)

• Quantitative Tverberg, Helly, & Carathéodory theorems
• Quantitative $(p,q)$ theorems in combinatorial geometry
• Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization
• Complexity of short Presburger arithmetic
• Helly numbers of Algebraic Subsets of ${\mathbb{R}}^d$
• Quantitative Tverberg theorems over lattices and other discrete sets
• Quantitative combinatorial geometry for continuous parameters