On the Integrality Gap of Binary Integer Programs with Gaussian Data

Sander Borst, Daniel Dadush, Sophie Huiberts +1

For a binary integer program (IP) $\max c^{\mathsf{T}}x,Ax\le b,x\in \{0,1{\}}^n$, where $A\in {\mathbb{R}}^{m\times n}$ and $c\in {\mathbb{R}}^n$ have independent Gaussian…