Hamiltonian cycles and the space of discounted occupational measures
Files
(Published version)
Date
2011
Authors
Eshragh Jahromi, Ali
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
thesis
Citation
Statement of Responsibility
Conference Name
Abstract
In 2000, a new polytope defined by the Discounted Occupational Measures (DOM) was developed for the Hamiltonian Cycle Problem (HCP). In this thesis, we exploit geometric properties of extreme points of that polytope. In particular, we refine the feasible region induced by that polytope into a narrower one. We show that the problem of finding a Hamiltonian cycle in a given graph is equivalent to the problem of finding a common extreme point of two especially constructed polytopes. Correspondingly, we develop new optimization models, as well as, random walk algorithms, to solve HCP. In addition, we develop a new hybrid algorithm for the HCP by synthesising DOM and the Cross Entropy method. Finally, we present algebraic properties of the class of stochastic matrices induced by a Hamiltonian cycle. These theoretical results are used to develop a new polytope containing all possible Hamiltonian solutions corresponding to a given graph.
School/Discipline
School of Mathematics and Statistics
Dissertation Note
Thesis (PhDMathematics)--University of South Australia, [2011].
Provenance
Copyright [2011] Ali Eshragh Jahromi
Description
xix, 136 leaves
ill.
Includes bibliographic references (p. 132-136)
ill.
Includes bibliographic references (p. 132-136)
Access Status
506 0#$fstar $2Unrestricted online access