1 citations · 1 across the 6 of their papers we have counts for
13 papers
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}…
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…
Counting Lattice Triangulations
Volker Kaibel, Günter M. Ziegler
We discuss the problem to count, or, more modestly, to estimate the number f(m,n) of unimodular triangulations of the planar grid of size . Among other tools, we employ…