Abstract
The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions to 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 bounded polyhedron {x : Ax<=b} contains exactly k integer points, 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 as in 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.
Item Type: |
Article
|
Date Type: |
Publication |
Status: |
Published |
Schools: |
Mathematics |
Subjects: |
Q Science > QA Mathematics |
Publisher: |
Springer Verlag |
ISSN: |
0209-9683 |
Date of First Compliant Deposit: |
30 March 2016 |
Date of Acceptance: |
12 February 2015 |
Last Modified: |
24 Jan 2021 08:40 |
URI: |
http://orca.cf.ac.uk/id/eprint/87665 |
Citation Data
Cited 5 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |