2020/12/15 by Sander Borst, Borst, Sander, Daniel Dadush +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #cs.DS #math.OC
paper · pdf · doi:10.48550/arxiv.2012.08346
openalex publication_date 2020/12/15 · arxiv created 2021/06/02 · arxiv updated 2021/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
For a binary integer program (IP) \rm max ~ cT x, Ax ≤ b, x ∈ \0,1\n, where A ∈ ℝm × n and c ∈ ℝn have independent Gaussian entries and the right-hand side b ∈ ℝ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-2/n7-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 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 npoly(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.