Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A quantitative Doignon-Bell-Scarf theorem

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

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


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

Citation Data

Cited 5 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics