Hamiltonian Cycles and the Space of Discounted Occupational Measures: Investigating Hamiltonian Cycles through Extreme Points of Certain Polytopes by Random Walks - Softcover

Eshragh, Ali

Softcover

ISBN 10: 3846548871 ISBN 13: 9783846548875

Verlag: LAP LAMBERT Academic Publishing, 2011

Inhaltsangabe

In 2000, a new polytope defined by the Discounted Occupational Measures (DOM) was developed for the Hamiltonian Cycle Problem (HCP). In this monograph, 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.

Über diesen Titel

Über die Autorin bzw. den Autor

Dr Ali Eshragh received his B.Sc. and M.Sc. in industrial engineering from Sharif University of Technology, Tehran. In 2008, he was awarded the IPRS scholarship to pursue his PhD at the University of South Australia, Adelaide. He received his PhD in August, 2011. He is currently a postdoctoral research fellow at the University of Adelaide.

Details zur Ausgabe

• Verlag: LAP LAMBERT Academic Publishing
• Erscheinungsdatum: 2011
• Sprache: Englisch
• ISBN 10: 3846548871
• ISBN 13: 9783846548875
• Einband: Taschenbuch
• Anzahl der Seiten: 168
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Alphascript Publishing; customerservice@vdm-vsg.de; ; Brivibas gatve 197; Riga; 1039; Lettland