  


Random halfintegral polytopes
Gábor Braun (braungrenyi.hu) Abstract: We show that halfintegral polytopes obtained as the convex hull of a random set of halfintegral points of the 0/1 cube have rank as high as Ω(logn/loglogn) with positive probability — even if the size of the set relative to the total number of halfintegral points of the cube tends to 0. The high rank is due to certain obstructions. We determine the exact threshold number, when these obstructions cease to exist. Keywords: combinatorial optimization, admissible cuttingplane procedures, random polytopes, integer programming Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Integer Programming (01 Programming ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: Download: [PDF] Entry Submitted: 11/13/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  