2014/05/11 by Iskander Aliev, Aliev, Iskander, Robert Bassett +5 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1405.2480
openalex publication_date 2014/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ≤ 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) = 2n 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.