论文标题
通过差异的随机整数程序的整体差距
Integrality Gaps for Random Integer Programs via Discrepancy
论文作者
论文摘要
我们证明了随机整数程序的值$ \ max c^tx，\ ax \ leq b，\ x \ in \ {0,1 \}^n $具有$ m $约束的新界限，\ ax \ leq b，\ x \ in \ {0,1 \}^n $与（a，b，c）$的$ m $限制因素和其线性编程放松。我们是由Dey，Dubey和Molinaro（Soda '21）的工作激励的，他们为将分支和结合树（B＆B）树的大小与添加剂完整性差距联系起来提供了框架。 Dyer和Frieze（Mor '89）和Borst等。 （数学编程'22）分别表明，对于某些随机包装和高斯IP，$ a，c $的条目是根据$ [0,1] $的均匀分布或高斯分布$ \ Mathcal {n}（n}（n}（0,1）$的均匀性，概率的prob by d n n n n / o o o_mmmm（\ o o_mmmmme）的均匀分布或高斯分布$^2 N / $ 1-1/n-e^{ - ω_m（1）} $。在本文中，我们将这些结果推广到$ a $的条目以整数间隔均匀分布（例如，$ \ { - 1,0,1,1 \} $），而$ a $的列的列是根据同位素logConcave分布分布的。其次，与先前工作的不变概率相比，我们将成功概率显着提高到$ 1-1/poly（n）$（取决于$ m $）。利用与分支结合的连接，我们的差距结果表明，对于这些IPS B＆B树具有较高概率的尺寸$ n^{poly（m）} $（即，对于固定$ m $的多项式），这大大扩展了b＆b的IPS类。 我们的主要技术贡献是一种新的线性差异定理，用于随机矩阵。我们的定理给出了目标向量等于或非常接近$ \ {0,1 \} $组合的一般条件，随机矩阵$ a $的列组合。证明使用了傅里叶分析方法，基于Hoberg和Rothvoss（Soda '19）以及Franks and Saks（RSA '20）的工作。
We prove new bounds on the additive gap between the value of a random integer program $\max c^Tx,\ Ax\leq b,\ x\in\{0,1\}^n$ with $m$ constraints and that of its linear programming relaxation for a wide range of distributions on $(A,b,c)$ . We are motivated by the work of Dey, Dubey, and Molinaro (SODA '21), who gave a framework for relating the size of Branch-and-Bound (B&B) trees to additive integrality gaps. Dyer and Frieze (MOR '89) and Borst et al. (Mathematical Programming '22), respectively, showed that for certain random packing and Gaussian IPs, where the entries of $A,c$ are independently distributed according to either the uniform distribution on $[0,1]$ or the Gaussian distribution $\mathcal{N}(0,1)$, the integrality gap is bounded by $O_m(\log^2 n / n)$ with probability at least $1-1/n-e^{-Ω_m(1)}$. In this paper, we generalize these results to the case where the entries of $A$ are uniformly distributed on an integer interval (e.g., entries in $\{-1,0,1\}$), and where the columns of $A$ are distributed according to an isotropic logconcave distribution. Second, we substantially improve the success probability to $1-1/poly(n)$, compared to constant probability in prior works (depending on $m$). Leveraging the connection to Branch-and-Bound, our gap results imply that for these IPs B&B trees have size $n^{poly(m)}$ with high probability (i.e., polynomial for fixed $m$), which significantly extends the class of IPs for which B&B is known to be polynomial. Our main technical contribution is a new linear discrepancy theorem for random matrices. Our theorem gives general conditions under which a target vector is equal to or very close to a $\{0,1\}$ combination of the columns of a random matrix $A$ . The proof uses a Fourier analytic approach, building on work of Hoberg and Rothvoss (SODA '19) and Franks and Saks (RSA '20).
