2 citations · 4 across the 8 of their papers we have counts for
14 papers · 1 filter
Extended Formulations for Packing and Partitioning Orbitopes
Yuri Faenza, Volker Kaibel
We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in (Kaibel and Pfetsch, 2008). Th…
On cardinality constrained cycle and path polytopes
Volker Kaibel, Ruediger Stephan
Given a directed graph D = (N, A) and a sequence of positive integers 1 <= c_1 < c_2 < ... < c_m <= |N|, we consider those path and cycle polytopes that are defined as the convex h…
Revlex-Initial 0/1-Polytopes
Volker Kaibel, Rafael Mechtel
We introduce revlex-initial 0/1-polytopes as the convex hulls of reverse-lexicographically initial subsets of 0/1-vectors. These polytopes are special knapsack-polytopes. It turns…
Low-dimensional faces of random 0/1-polytopes
Volker Kaibel
Let P be a random -dimensional 0/1-polytope with vertices, and denote by the \emph{-face density} of , i.e., the quotient of the number of -dimensional…
The Simplex Algorithm in Dimension Three
Volker Kaibel, Rafael Mechtel, Micha Sharir +1
We investigate the worst-case behavior of the simplex algorithm on linear programs with three variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we c…
On the graph-density of random 0/1-polytopes
Volker Kaibel, Anja Remshagen
Let X_{d,n} be an n-element subset of {0,1}^d chosen uniformly at random, and denote by P_{d,n} := conv X_{d,n} its convex hull. Let D_{d,n} be the density of the graph of P_{d,n}…