Springe direkt zu Inhalt

On lattice points in strictly convex sets and Helly-type numbers in integer programming

10.12.2015 | 14:15
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