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.