Further talks

Modal title

Modal content

Date / Time

Speaker

Title

Location

2 February 2016
11:00-12:00

Dr. Stefan Weltge
Otto-von-Guericke Universität Magdeburg, Deutschland

Details

Title	Improved Bounds on Doignon-Bell-Scarf Numbers
Speaker, Affiliation	Dr. Stefan Weltge, Otto-von-Guericke Universität Magdeburg, Deutschland
Date, Time	2 February 2016, 11:00-12:00
Location	HG G 19.2
Abstract	Given a discrete subset S of R^n, let c(S, k) be the smallest number t such that for every finite system of linear inequalities that has exactly k solutions in S, there exists a subsystem of at most t inequalities that still has exactly k solutions in S. For the case of S = Z^n, this number was introduced by Aliev et al. (2014) who showed that c(Z^n,k) = O(k) holds for every n. Recently, Chestnut, Hildebrand & Zenklusen (2015) improved this to c(Z^n, k) = O(k * log log k / log^{1/3}). In addition, they provided a lower bound showing that c(Z^n,k) = Omega(k^{(n-1)/(n+1)}) holds for every n. We improve on the previous upper bounds in two ways. First, we close the gap for Z^n and show that the lower bound of Chestnut et al. is asymptotically tight for all n. Second, we generalize the result of Aliev et al. to general discrete sets S with \|S\| >= 2 and improve the bound to c(S, k) <= floor{(k+1)/2)} * (h(S) - 2) + h(S) for all k <= \|S\|, where h(S) is the Helly-number of S.

Improved Bounds on Doignon-Bell-Scarf Numbersread_more

Notes: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archive: undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined