A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm (Q1974584)

The paper gives a lower bound on the average number of steps the simplex method needs to solve an LP problem. The important feature of the result is that it is valid for all variants of the simplex method. Variants differ from each other in the rule how they determine the `next vertex'. The problem under investigation is: \(\max v^T x\) subject to \(a_1^T x \leq 1, \dots, a_m^T \leq 1\), where all vectors are in \(\mathbb{R}^n\) and \(m\geq n\). Additionally, the problems are randomly generated according to the rotation symmetry model, i.e., \(a_1,\dots, a_m\) and \(v\) are independently, identically and symmetrically distributed under rotations on \(\mathbb{R}^n \setminus \{0\}\). For the expected number of steps of the simplex method the following lower bound is attained: \(E_{m,n} [s^{var}] \geq C m^{1/(n-1)} n^0\) for all pairs \(m\geq n\) and for all variants, where \(C\) is a constant.