BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230630T120000Z
UID:5e51441c2fea4991b59d1fef9650902a-476
DTSTAMP:19700101T120016Z
DESCRIPTION:Integrality Gaps for Random Integer Programs via Discrepancy
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/476/integrality-gaps-for-random-integer-programs-via-discrepancy/
SUMMARY:We prove new bounds on the additive gap between the value of a random integer program max cTx, Ax≤b, x∈{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 N(0,1), the integrality gap is bounded by Om(log2n/n) with probability at least 1−1/n−e-Ω(m). 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 npoly(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).   

Joint work with Sander Borst (CWI) and Dan Mikunlincer (MIT).


Microsoft Teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rachana Gusain, Rahul Madhavan, Rameesh Paul, KVN Sreenivas
DTSTART:20230630T120000Z
END:VEVENT
END:VCALENDAR