Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem
| Autor: | Robert Hildebrand, Rico Zenklusen, Stephen R. Chestnut |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Sublinear function General Mathematics 010102 general mathematics Dimension (graph theory) 01 natural sciences Upper and lower bounds Helly theorem integer programming lattice points 010101 applied mathematics Combinatorics Linear inequality Polyhedron Helly's theorem Integer Optimization and Control (math.OC) FOS: Mathematics 0101 mathematics Integer programming Mathematics - Optimization and Control Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics, 32 (1) |
| DOI: | 10.48550/arxiv.1512.07126 |
| Popis: | The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [Combinatorica, 37 (2017), pp. 313--332] generalizes the famous Doignon--Bell--Scarf theorem on the existence of integer solutions to systems of linear inequalities. Their generalization examines the number of facets of a polyhedron that contains exactly $k$ integer points in ${R}^n$. They show that there exists a number $c(n,k)$ such that any polyhedron in $\mathbb{R}^n$ that contains exactly $k$ integer points has a relaxation to at most $c(n,k)$ of its inequalities that will define a new polyhedron with the same integer points. They prove that $c(n,k) = O(k)2^n$. In this paper, we improve the bound asymptotically to be sublinear in $k$, that is, $c(n,k) = o(k) 2^n$. We also provide lower bounds on $c(n,k)$, along with other structural results. For dimension n=2, our upper and lower bounds match to within a constant factor. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|