• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Integer Programming and Combinatorial Optimization >On the Integrality Gap of Binary Integer Programs with Gaussian Data
【24h】

On the Integrality Gap of Binary Integer Programs with Gaussian Data

机译：关于高斯数据二元整数程序的完整性差距

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

For a binary integer program (IP) max c~Tx, Ax ≤ b, x ∈ {0, 1}~n, where A ∈ R~(m×n) and c∈R~n have independent Gaussian entries and the right-hand side b ∈ R~m satisfies that its negative coordinates have ℓ_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 poly(m)(log n)~2/n with probability at least 1 - 1/n~7 - 2~(-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 poly-nomially on m instead of exponentially. By recent breakthrough work of Dey, Dubey and Molinaro (SODA, 2021), the bound on the integrality gap immediately implies that branch and bound requires n~(poly(m)) time on random Gaussian IPs with good probability, which is polynomial when the number of constraints m is fixed.
机译：对于二进制整数程序（IP）max c〜tx，x≤b，x∈{0，1}〜n，其中a∈r〜（m×n）和c∈r〜n具有独立的高斯条目和右侧 -Hand侧面B∈R〜M满足其负坐标，最多有N / 10具有ℓ_2标准，我们证明了线性编程放松的值与IP之间的间隙是由Poly（M）的上限（log n） 〜2 / n具有至少1 - 1 / N〜7 - 2〜（ - 聚（m））。 我们的结果提供了一种高斯模拟的戴尔和Frieze（Math。o.r.，1989）的古典积分差距结果，在随机包装IPS的情况下。 在限制包装案例中，我们的完整性差距仅取决于多个版本而不是指数。 通过近期Dey，Dubey和Molinaro（SODA，2021）的突破性工作，完整性差距的界限立即意味着分支和绑定需要N〜（Poly（M））在随机高斯IP上具有良好概率的时间，这是多项式的 限制M的数量是固定的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号