Convex hulls of sets of 0/1-vectors (0/1-polytopes) form the backbone of Polyhedral Combinatorics. Over the last four decades, extensive research on special 0/1-plytopes has lead to tremendous improvements in the solution of combinatorial optimization problems. The goal of this project is to better understand the class of 0/1-polytopes. Our vision is to finally utilize general geometric and combinatorial insights for concrete combinatorial (optimization) problems.
Publications
- Kaibel, Volker. On the expansion of graphs of 0/1-polytopes. In: The sharpest cut, Grötschel, Martin (Eds.), pp. 199–216, SIAM, Philadelphia, PA, 2004.
- Kaibel, Volker, Remshagen, Anja. On the graph-density of random 0/1-polytopes. In: Proc. RANDOM 03, Princeton, volume 2764 of LNCS, pp. 318–328, Springer, 2003.
- Kaibel, Volker. Low-dimensional faces of random 0/1-polytopes. In: Proc. IPCO X, New York, volume 3064 of LNCS, pp. 401-415, Springer, 2004.
- Kaibel, Volker, Gillmann, Rafael. Revlex-Initial 0/1-Polytopes. J. Comb. Theory, Ser. A, 113:799–821, 2006.
- Gillmann, Rafael. 0/1-Polytopes: Typical and Extremal Properties. PhD Thesis, TU Berlin, 2006.
Partners
Rafael Gillmann (TU Berlin)
Günter M. Ziegler (TU Berlin)
Funding
DFG Research Group Algorithms
Structure
Randomness