Reference : A Quantitative Doignon-Bell-Scarf theorem
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
A Quantitative Doignon-Bell-Scarf theorem
Aliev, Iskander [Cardiff University > Mathematics Department > > >]
Bassett, Robert [University of California, Davis - UC Davis > Department of Mathematics > > >]
De Loera, Jesus [University of California, Davis - UC Davis > Department of Mathematics > > >]
Louveaux, Quentin mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Springer Science & Business Media B.V.
Yes (verified by ORBi)
[en] Lattice points ; Polyhedra
[en] 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 on the number k, such that if a bounded polyhedron {x in R^n : 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.

File(s) associated to this reference

Fulltext file(s):

Open access
Quantitative_DBS.pdfAuthor postprint239.26 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.