The least-used direction pivot rule on acyclic unique sink orientations.

摘要

The least-used direction (LUD) rule is one of a class of largely unanalyzed pivot rules - the history-based rules. History-based pivot rules guide the progression of edge following algorithms like the Simplex method. This thesis investigates the problem of finding an exponential length LUD path on a particular kind of digraph known as an acyclic unique sink orientation of a hypercube (AUSO). In addition, a survey of six well-known history-based pivot rule and examples to illustrate their independence is given. The Fibonacci construction is introduced as a potential way of creating families of AUSOs that allows for exponential LUD paths. The most straight-forward application of this technique is unsuccessful, but there is room for more exploration. An exponential lower bound is given for the number of times the least-used direction is used by a Hamiltonian path following the related history-based Zadeh's rule. This result shows that the number of times each direction is used grows at a similar rate and is thus relatively balanced.