The least-used direction pivot rule on acyclic unique sink orientations |
Posted on:2012-08-09 | Degree:M.Sc | Type:Thesis |
University:McGill University (Canada) | Candidate:Deering, Theresa Kiyoko | Full Text:PDF |
GTID:2466390011965842 | Subject:Computer Science |
Abstract/Summary: | |
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. |
Keywords/Search Tags: | Direction, Pivot, Rule, LUD, History-based |
|
Related items |