A Discrepancy based Approach to Integer Programming

Details A Discrepancy based Approach to Integer Programming A Discrepancy based Approach to Integer Programming

2011-11-20

arxiv.org/abs/1111.4649v2

Computer Science

Data Structures and Algorithms

Scientific paper

We consider integer programs on polytopes in R^n with m facets whose normal vectors are chosen independently from any spherically symmetric distribution. We show that for m at most 2^(sqrt(n)), there exist constants c_1 < c_2 such that with high probability, this random IP is infeasible if the largest ball contained in the corresponding polytope has radius less than c_1sqrt(log(2m/n)) and it is feasible if the radius is at least c_2sqrt(log(2m/n)). Thus, a transition from infeasibility to feasibility happens within a constant factor increase in the radius. Moreover, if the polytope contains a ball of radius Omega(log(2m/n)), then there is a randomized polynomial-time algorithm to find an integer solution with high probability (over the input). Our main tools are: a new connection between integer programming and matrix discrepancy, a bound on the discrepancy of random Gaussian matrices and Bansal's algorithm for finding low-discrepancy solutions.

Affiliated with

Also associated with

No associations

Rating

A Discrepancy based Approach to Integer Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Discrepancy based Approach to Integer Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Discrepancy based Approach to Integer Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-130296