On the shadow simplex method for curved polyhedra (Q728496)

The shadow simplex has been at the heart of many theoretical attempts to explain the efficiency of the simplex method in practice. This paper deals with the simplex method over polyhedra satisfying certain ``discrete curvature'' lower bounds and the analysis is based on a dual perspective. A new type of dual analysis of the shadow simplex method is developed which provides a clean and powerful tool for improving all previously mentioned results. For linear optimization, given an initial feasible vertex, it is shown that an optimal vertex can be found using an expected \(O(\frac{n^{3}}{\delta} \ln\frac{n}{\delta})\) simplex pivots, each requiring \(O(mn)\) time to compute, where \(m\) is the number of constraints.