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 thenumber 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. / La règle de least-used direction (LUD) fait parti de la grande classe des règles pivots history-based. Ceux-ci guident la progression des algorithmes de détection des contours, tel que la méthode Simplex. Ce mémoire examine le problème de la recherche de chemin LUD de longueur exponentielle dans un graphe acyclique dirigé à bloc récepteur unique (acyclic unique sink orientation - AUSO) dans les hypercubes. De plus, une vue d'ensemble de six règles pivots history-based ainsi que des exemples sont fournis pour illustrer leurs indépendances. La structure Fibonacci est présentée comme une possibilité de créer des familles de graphe acyclique dirigé à bloc récepteur unique permettant des chemins LUD de longueurs exponentielles. Exécuter cette technique de façon simple s'avère infructueuse, par contre cela nous laisse la place à plus d'amples explorations. Une borne inférieure exponentielle est fournie pour le nombre de fois que LUD est présent dans un chemin Hamiltonian selon la règle history-based Zadeh. Les résultats obtenus démontrent que le nombre de fois utilisé par chaque direction augmente à une fréquence semblable et est donc relativement équilibré.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.97171 |
| Date | January 2011 |
| Creators | Deering, Theresa |
| Contributors | David Avis (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0016 seconds