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 and Loveaux, Quentin 2017. A quantitative Doignon-Bell-Scarf theorem. Combinatorica 37 (3) , pp. 313-332. 10.1007/s00493-015-3266-9

[img]
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 Edit Item

Downloads

Downloads per month over past year

View more statistics