0/1 Polytopes with Quadratic Chvatal Rank

Details 0/1 Polytopes with Quadratic Chvatal Rank 0/1 Polytopes with Quadratic Chvatal Rank

2012-04-20

arxiv.org/abs/1204.4753v1

Mathematics

Combinatorics

15 pages, 2 figures

Scientific paper

For a polytope P, the Chvatal closure P' is obtained by simultaneously strengthening all feasible inequalities cx <= b (with integral c) to cx <= floor(b). The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvatal rank. If P is a subset of [0,1]^n, then it is known that O(n^2 log n) iterations always suffice (Eisenbrand and Schulz (1999)) and at least (1+1/e-o(1))n iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving a huge gap between lower and upper bounds. We prove that there is a polytope contained in the 0/1 cube that has Chvatal rank Omega(n^2), closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by several authors. Our choice of P is the convex hull of a semi-random Knapsack polytope and a single fractional vertex. The main technical ingredient is linking the Chvatal rank to simultaneous Diophantine approximations w.r.t. the L1-norm of the normal vector defining P.

Affiliated with

Also associated with

No associations

Rating

0/1 Polytopes with Quadratic Chvatal Rank 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 0/1 Polytopes with Quadratic Chvatal Rank, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 0/1 Polytopes with Quadratic Chvatal Rank will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729441