Integrality gaps for random integer programs via discrepancy.

In this work, we prove new bounds on the additive gap between the value of a random integer program maxcTx,Ax≤b,x∈{0,1}nwithmconstraints and that of its linear programming relaxation for a wide range of distributions on(A,b,c).Our investigation is motivated by the work of Dey, Dubey, and Molinaro (SODA ’21), who gave a framework for relatingthe 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 certainrandom packing and Gaussian IPs, where the entries ofA,care independently distributed according to either the uniformdistribution on[0,1]or the Gaussian distributionN(0,1), the integrality gap is bounded byOm(log2n/n)with probabilityat least 1−1/n−e−Ωm(1). In this paper, we generalize these results to the cases where the entries ofAare uniformlydistributed on an integer interval (e.g., entries in{−1,0,1}), and where the columns ofAare distributed according to anisotropic logconcave distribution. Second, we substantially improve the success probability to 1−1/poly(n), comparedto constant probability in prior works (depending onm). Leveraging the connection to Branch-and-Bound, our gap resultsimply that for these IPs B&B trees have sizenpoly(m)with high probability (i.e., polynomial for fixedm), which significantlyextends the class of IPs for which B&B is known to be polynomial.Our main technical contribution and the key to achieving the above results is a new linear discrepancy theorem forrandom 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 matrixA. Compared to prior results, our theorem handles a much wider rangeof distributions onA, both continuous and discrete, and achieves success probability exponentially close to 1, as opposedto the constant probability shown in earlier results. Our proof uses a Fourier analytic approach, building on the work ofHoberg and Rothvoss (SODA ’19) and Franks and Saks (RSA ’20) who studied the discrepancy of random set systems andmatrices respectively.

• View at Publisher

Free Full Text ( Final Version , 706kb )

See Also
techReport Integrality gaps for random integer programs via discrepancy S.J. Borst (Sander), D.N. Dadush (Daniel) and D. Mikulincer (Dan)