On lattice points in strictly convex sets and Helly-type numbers in integer programming
Doignon proved a discrete version of Helly's theorem claiming that a finite family of convex sets in R^n intersects in an integral point if every subfamily of size at most 2^n does so. Motivated by applications in integer programming, Aliev et al. recently obtained a quantitative version of this result, which guarantees that a finite family of convex sets intersects in k integral points whenever every subfamily of size at most c_n(k) does so. The best current upper bound on the minimal such constant c_n(k) grows linearly with the parameter k. Based on a connection to the number of boundary integral points in strictly convex sets, we show that the asymptotic behavior of c_n(k) is sublinear in dimension two and we determine the exact value of c_n(k) for k at most four. ------
WHEN: 10.12.15 at 14:15
WHERE: Seminar Room, Arnimallee 2, FU Berlin
Zeit & Ort
10.12.2015 | 14:15
Seminar Room, Arnimallee 2, FU Berlin