Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652757 | Electronic Notes in Discrete Mathematics | 2010 | 8 Pages |
Abstract
We will show that random half-integral polytopes contain certain sets Fk with high probability, the sets of k-tuples with entries in , and exactly one entry equal to . We precisely determine the threshold number k for which the phase transition occurs. Using these random polytopes we show that establishing integer-infeasibility takes rounds of (almost) any cutting-plane procedure with high probability whenever the number of vertices is θ(n3). As a corollary, a relationship between the number of vertices and the rank of the polytope with respect to (almost) any cutting-plane procedure follows.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics