Articles liés à Hamiltonian Cycles and the Space of Discounted Occupational...

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

Eshragh, Ali

 
9783846548875: Hamiltonian Cycles and the Space of Discounted Occupational Measures: Investigating Hamiltonian Cycles through Extreme Points of Certain Polytopes by Random Walks
Couverture souple
ISBN 10 : 3846548871 ISBN 13 : 9783846548875
Editeur : LAP LAMBERT Academic Publishing, 2011

Synopsis

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.

Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.

Présentation de l'éditeur

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.

Biographie de l'auteur

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.

Les informations fournies dans la section « A propos du livre » peuvent faire référence à une autre édition de ce titre.

Éditeur
LAP LAMBERT Academic Publishing
Date d'édition
2011
Langue
anglais
ISBN 10 
3846548871
ISBN 13 
9783846548875
Reliure
Broché
Nombre de pages
168
Coordonnées du fabricant
non disponible
Personne responsable
KreGa Onlinehandel GmbH
4950000000000
info@krega-onlinehandel.de

Birkenweg 31
Brakel
33034
Allemagne