Integer feasibility of random polytopes: random integer programs
From MaRDI portal
Abstract: We study integer programming instances over polytopes P(A,b)={x:Ax<=b} where the constraint matrix A is random, i.e., its entries are i.i.d. Gaussian or, more generally, its rows are i.i.d. from a spherically symmetric distribution. The radius of the largest inscribed ball is closely related to the existence of integer points in the polytope. We show that for m=2^O(sqrt{n}), there exist constants c_0 < c_1 such that with high probability, random polytopes are integer feasible if the radius of the largest ball contained in the polytope is at least c_1sqrt{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 c_0sqrt{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. We show integer feasibility via 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 (Lovett-Meka, FOCS '12) to give a constructive upper bound on the linear discrepancy of random matrices. By our connection between discrepancy and integer feasibility, this upper bound on linear discrepancy translates to the radius lower bound that guarantees integer feasibility of random polytopes.
Recommendations
Cites work
- scientific article; zbMATH DE number 1559544 (Why is no real title available?)
- (Leveled) fully homomorphic encryption without bootstrapping
- A hierarchy of polynomial time lattice basis reduction algorithms
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Bounds for Width Two Branching Programs
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- Evaluating Branching Programs on Encrypted Data
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
- Fully homomorphic encryption using ideal lattices
- Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
- New lattice-based cryptographic constructions
- On lattices, learning with errors, random linear codes, and cryptography
- On lattices, learning with errors, random linear codes, and cryptography
- Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
- Public-key cryptosystems from the worst-case shortest vector problem
- Toward basing fully homomorphic encryption on worst-case hardness
- Trapdoors for hard lattices and new cryptographic constructions
- Trapdoors for lattices: simpler, tighter, faster, smaller
Cited in
(10)- Weaver's discrepancy for Gaussian random vectors
- Algorithmic obstructions in the random number partitioning problem
- The discrepancy of random rectangular matrices
- Smoothed analysis of the Komlós conjecture: Rademacher noise
- Approaches for biobjective integer linear robust optimization
- On the integrality gap of binary integer programs with Gaussian data
- Proximity bounds for random integer programs
- Proximity bounds for random integer programs
- Investigation of solutions of randomly generated integer programming problems with 0-1 variables
- Zero-one laws for random feasibility problems
This page was built for publication: Integer feasibility of random polytopes: random integer programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988898)
