N&O seminar. Speaker: Sander Borst (CWI)
Title: On the Integrality Gap of Binary Integer Programs with Gaussian Data
Abstract: An analysis of binary integer programs with Gaussian data . In particular, we look at the gap between the value of the LP relaxation and the integer program, known as the integrality gap. We prove a high probability upper bound on the size of the integrality gap for IP's from this distribution. By a recent result, this implies that with high probability the Branch & Bound-algorithm solves these IP's in polynomial time (in the number of variables).
Please contact Sven Polak for the zoom link.
