Linear Programs Where Every Shadow Simplex Path is Exponentially Long

It remains open whether there is a version of the simplex method guaranteed to run in strongly polynomial time. One variant, the shadow simplex method, has been shown to have strongly polynomial expected run-time both for random linear programs and in the smoothed analysis model. The shadow simplex method solves a linear program by implicitly projecting the feasible region onto a two dimensional polygon. The choice of projection is not canonical, so for each method of choosing a projection one finds a different shadow simplex method. Examples are known in one which a single choice of projection leads to an exponential run-time, but the possibility has remained that one could construct a variant of the shadow simplex method that always chooses some projection guaranteeing a strongly polynomial run-time. We show that no such strongly polynomial time variant of the shadow simplex method exists by constructing families of linear programs where every choice of projection leads to an exponential run-time.