Aliev, Iskander  ORCID: https://orcid.org/0000-0002-2206-9207, 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
|
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: | 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: | 30 Nov 2024 13:15 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/87665 |
Citation Data
Cited 9 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |
Altmetric
Altmetric