On the Rational Polytopes with Chvatal Rank 1
We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP ∩ co-NP, an indication that it is probably not NP-complete. It is open whether there is a polynomial time algorithm to solve the … Read more