Title: Exponential lower bounds for history-based simplex pivot rules on abstract cubes,
Abstract: The behavior of the simplex algorithm is a widely studied subject.
Specifically, the question of the existence of a polynomial pivot rule for the
simplex algorithm is of major importance. Here, we give exponential lower
bounds for three history-based pivot rules. Those rules decide their next step
based on memory of the past steps. In particular, we study Zadeh's least
entered rule, Johnson's least-recently basic rule and Cunningham's
least-recently considered (or round-robin) rule. We give exponential lower
bounds on Acyclic Unique Sink Orientations (AUSO) of the abstract cube, for all
of these pivot rules. For Johnson's rule our bound is the first superpolynomial
one in any context; for Zadeh's it is the first one for AUSO. Those two are our
main results.