N&O Seminar: Sander Borst (CWI)

Everyone is welcome to attend this online N&O seminar, with Sander Borst. Title: On the Integrality Gap of Binary Integer Programs with Gaussian Data. Please contact Sven Polak for the zoom link.
  • What Networks & Optimization English
  • When 11-05-2021 from 13:00 to 14:00 (Europe/Amsterdam / UTC200)
  • Contact Name
  • Add event to calendar iCal

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.