A quantitative Doignon-Bell-Scarf theorem

Aliev, Iskander, Bassett, Robert, De Loera, Jesus and Loveaux, Quentin 2017. A quantitative Doignon-Bell-Scarf theorem. Combinatorica 37 (3) , pp. 313-332. 10.1007/s00493-015-3266-9

Preview

PDF - Accepted Post-Print Version Download (231kB) | Preview

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:	15 December 2014
Last Modified:	28 Jun 2019 05:08
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