TY - GEN
T1 - Integer feasibility of random polytopes
AU - Chandrasekaran, Karthekeyan
AU - Vempala, Santosh S.
PY - 2014
Y1 - 2014
N2 - We study the Chance-Constrained Integer Feasibility Problem, where the goal is to determine whether the random polytope P(A,b) = {x ∈ ℝn: Aix ≤ bi,i ∈ [m]} obtained by choosing the constraint matrix A and vector b from a known distribution is integer feasible with probability at least 1 - ε. We consider the case when the entries of the constraint matrix A are i.i.d. Gaussian (equiv-alently are i.i.d. from any spherically symmetric distribution). The radius of the largest inscribed ball is closely related to the existence of integer points in the polytope. We find that for m up to 2O(√2)) constraints (rows of A), there exist constants c0 < c1 such that with high probability (ε = 1/poly(n)), random polytopes are integer feasible if the radius of the largest ball contained in the polytope is at least c1 √log (m/n); and integer infeasible if the largest ball contained in the polytope is centered at (1/2,⋯, 1/2) and has radius at most c0 √log (m/n). Thus, random polytopes transition from having no integer points to being integer feasible within a constant factor increase in the radius of the largest inscribed ball. Integer feasibility is based on a randomized polynomial-time algorithm for finding an integer point in the polytope. Our main tool is a simple new connection between integer feasibility and linear discrepancy. We extend a recent algorithm for finding low-discrepancy solutions to give a constructive upper bound on the linear discrepancy of random Gaussian matrices. By our connection between discrepancy and integer feasibility, this upper bound on linear discrepancy translates to the radius bound that guarantees integer feasibility of random polytopes.
AB - We study the Chance-Constrained Integer Feasibility Problem, where the goal is to determine whether the random polytope P(A,b) = {x ∈ ℝn: Aix ≤ bi,i ∈ [m]} obtained by choosing the constraint matrix A and vector b from a known distribution is integer feasible with probability at least 1 - ε. We consider the case when the entries of the constraint matrix A are i.i.d. Gaussian (equiv-alently are i.i.d. from any spherically symmetric distribution). The radius of the largest inscribed ball is closely related to the existence of integer points in the polytope. We find that for m up to 2O(√2)) constraints (rows of A), there exist constants c0 < c1 such that with high probability (ε = 1/poly(n)), random polytopes are integer feasible if the radius of the largest ball contained in the polytope is at least c1 √log (m/n); and integer infeasible if the largest ball contained in the polytope is centered at (1/2,⋯, 1/2) and has radius at most c0 √log (m/n). Thus, random polytopes transition from having no integer points to being integer feasible within a constant factor increase in the radius of the largest inscribed ball. Integer feasibility is based on a randomized polynomial-time algorithm for finding an integer point in the polytope. Our main tool is a simple new connection between integer feasibility and linear discrepancy. We extend a recent algorithm for finding low-discrepancy solutions to give a constructive upper bound on the linear discrepancy of random Gaussian matrices. By our connection between discrepancy and integer feasibility, this upper bound on linear discrepancy translates to the radius bound that guarantees integer feasibility of random polytopes.
KW - Chance-Constrained Programs
KW - Discrepancy
KW - Integer Programming
KW - Probabilistic Instances
KW - Random Matrices
UR - http://www.scopus.com/inward/record.url?scp=84893316644&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893316644&partnerID=8YFLogxK
U2 - 10.1145/2554797.2554838
DO - 10.1145/2554797.2554838
M3 - Conference contribution
AN - SCOPUS:84893316644
SN - 9781450322430
T3 - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
SP - 449
EP - 458
BT - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PB - Association for Computing Machinery
T2 - 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
Y2 - 12 January 2014 through 14 January 2014
ER -