Random half-integral polytopes

DOI10.1016/J.ORL.2011.03.003MaRDI QIDQ635514zbMATH OpenOpenAlexFDO

Authors Gábor Braun, Sebastian Pokutta

Publication date 19 August 2011

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2011.03.003

zbMATH Keywords

cutting-plane proceduresrandom half-integral polytopesrank lower bounds

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10)

Recommendations

• Threshold phenomena for high-dimensional random polytopes
• On 0-1 polytopes with many facets
• 0/1-Polytopes. Typical and extremal properties
• On the convex hull of random points in a polytope
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3156817 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Chvátal closures for mixed integer programming problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Edmonds polytopes and a hierarchy of combinatorial problems
• Graph Theory and Probability
• On cutting-plane proofs in combinatorial optimization
• On the Chvátal rank of polytopes in the 0/1 cube
• On the matrix-cut rank of polyhedra.
• On the rank of cutting-plane proof systems
• Outline of an algorithm for integer solutions to linear programs
• Probability and Computing
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Valid inequalities for mixed integer linear programs

Cited in

(2)

• Integer feasibility of random polytopes: random integer programs
• Expansion of random 0/1 polytopes

This page was built for publication: Random half-integral polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q635514)