Name
Abstract | ||
|---|---|---|
The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [Combmatorica, 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 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/16M1100095 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
Helly theorem,integer programming,lattice points | Sublinear function,Integer,Discrete mathematics,Mathematical optimization,Combinatorics,Existential quantification,Polyhedron,Linear inequality,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 1 | 0895-4801 |
Citations | PageRank | References |
3 | 0.45 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephen R. Chestnut | 1 | 48 | 5.77 |
| Robert Hildebrand | 2 | 69 | 7.82 |
| Rico Zenklusen | 3 | 307 | 33.70 |