论文标题
关于使用高斯数据的二进制整数程序的完整性差距
On the Integrality Gap of Binary Integer Programs with Gaussian Data
论文作者
论文摘要
对于二进制整数程序（ip）$ {\ rm max} 〜c^\ mathsf {t} x，ax \ leq b，x \ in \ {0,1 \}^n $，其中$ a \ in \ in \ in \ mathbb {r}右侧$ b \ in \ mathbb {r}^m $满足其负坐标的$ \ ell_2 $ norm，最多最多$ n / 10 $，我们证明，线性编程放松的价值与IP的价值与IP的上限之间的差距是由$ \ propatatOrname {m）（\ poly}（py log n）（\ log n）（\ l log n）^2 / n $限制$ 1-2/n^7-2^{ - \ operatorName {poly}（m）} $。我们的结果给出了在随机填料IP的情况下，染色和frize的经典完整性差距（Math。O.R.，1989）的高斯类似物。在对包装案例的约束中，我们的完整性差距仅取决于$ m $而不是指数级。在最近的Dey，Dubey和Molinaro（Soda，2021）的突破性工作的基础上，我们表明完整性差距意味着分支机构需要$ n^{\ permatatorName {\ permatatorname {poly}（m m）} $ time在随机高斯ips上的时间，良好的可能性，当时是polynomial，这是polynomial nignomial nivel n offerents $ m $ m $ m $ $ mes $ mes $ mes $ $ n is nes nes nes n of nes n of n $ m $。我们通过一种新型的元理论得出了这个结果，该元理论将分支和结合树的大小与随机LogConcave IP的整体差距相关联。
For a binary integer program (IP) ${\rm max} ~ c^\mathsf{T} x, Ax \leq b, x \in \{0,1\}^n$, where $A \in \mathbb{R}^{m \times n}$ and $c \in \mathbb{R}^n$ have independent Gaussian entries and the right-hand side $b \in \mathbb{R}^m$ satisfies that its negative coordinates have $\ell_2$ norm at most $n/10$, we prove that the gap between the value of the linear programming relaxation and the IP is upper bounded by $\operatorname{poly}(m)(\log n)^2 / n$ with probability at least $1-2/n^7-2^{-\operatorname{poly}(m)}$. Our results give a Gaussian analogue of the classical integrality gap result of Dyer and Frieze (Math. of O.R., 1989) in the case of random packing IPs. In constrast to the packing case, our integrality gap depends only polynomially on $m$ instead of exponentially. Building upon recent breakthrough work of Dey, Dubey and Molinaro (SODA, 2021), we show that the integrality gap implies that branch-and-bound requires $n^{\operatorname{poly}(m)}$ time on random Gaussian IPs with good probability, which is polynomial when the number of constraints $m$ is fixed. We derive this result via a novel meta-theorem, which relates the size of branch-and-bound trees and the integrality gap for random logconcave IPs.
