Integrality Gaps for Random Integer Programs via Discrepancy

Sander Borst, Daniel Dadush, Dan Mikulincer

We prove new bounds on the additive gap between the value of a random integer program $\max c^{T}x,Ax\le b,x\in \{0,1{\}}^n$ with $m$ constraints and that of its linear programming…