Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The integrality gap of random binary integer programs

Mathematics of Data & Decisions

Speaker: Sophie Huiberts, Centrum Wiskunde & Informatica (CWI)
Related Webpage: https://sophie.huiberts.me/
Location:
Start time: Tue, Feb 23 2021, 9:30AM

We bound the integrality gap of binary integer programs max c^T x, Ax≤b, x∈{0,1}^n, where A and c have independent Gaussian entries. By a recent breakthrough work of Dey, Dubey and Molinaro (SODA 2021), this implies that branch and bound requires a tree of size n^poly(m) on random Gaussian IP's with good probability. When m is fixed, this quantity is polynomial.