On the integrality gap of binary integer programs with Gaussian data

• 成果类型: Article
• 署名作者: Borst, Sander; Dadush, Daniel; Huiberts, Sophie; Tiwari, Samarth
• 署名单位: Centrum Wiskunde & Informatica (CWI)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01828-1
• 发表日期: 2023
• 页码: 1221-1263
• 关键词: probabilistic analysis; complexity

摘要

For a binary integer program (IP) max c(T)x, Ax <= b, x is an element of {0, 1}(n), where A is an element of R-mxn and c is an element of R-n have independent Gaussian entries and the right-hand side b is an element of R-m satisfies that its negative coordinates have l(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 - 2/n(7) - 2(-poly(m)). Our results give a Gaussian analogue of the classical integrality gap result of Dyer and Frieze (Math OR, 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(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.