2 citations · 4 across the 8 of their papers we have counts for
4 papers · 1 filter
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}…
The Random Edge Rule on Three-Dimensional Linear Programs
Volker Kaibel, Raphael Mechtel, Micha Sharir +1
The worst-case expected length f(n) of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be b…