| Vorliegende Sprache |
eng |
| Hinweise auf parallele Ausgaben |
364876441 Buchausg. u.d.T.: ‡Hamiltonian cycle problem and Markov chains |
| ISBN |
978-1-4614-3231-9 |
| Name |
Borkar, Vivek S. |
| Ejov, Vladimir |
| Name ANZEIGE DER KETTE |
Ejov, Vladimir |
| Name |
Filar, Jerzy A. |
| Nguyen, Giang T. |
| T I T E L |
Hamiltonian Cycle Problem and Markov Chains |
| Verlagsort |
New York, NY |
| Verlag |
Springer New York |
| Erscheinungsjahr |
2012 |
| 2012 |
| Umfang |
Online-Ressource (XIV, 201p. 82 illus., 31 illus. in color, digital) |
| Reihe |
International Series in Operations Research & Management Science ; 171 |
| Notiz / Fußnoten |
Description based upon print version of record |
| Weiterer Inhalt |
Preface; Acknowledgements; Contents; Part I Motivating Phenomena; Chapter 1 Illustrative Graphs; 1.1 The Graph That Started It All; 1.2 A Sample of Distinctive Graphs; 1.3 Co-spectral Graphs; Chapter 2 Intriguing Properties; 2.1 Preliminaries and Notation; 2.2 Fractal-like Structure of Graphs; 2.3 Invariants of Graphs; Part II Probabilistic Approaches; Chapter 3 Markov Chains; 3.1 Introduction; 3.2 Markov Chains and Perturbations; 3.3 Hitting Times and the Fundamental Matrix; 3.4 Hamiltonian Cycles as Hitting Time Variance Minimisers; Chapter 4 Markov Decision Processes; 4.1 Introduction. 4.2 Markov Decision Processes4.3 Occupational Measures; 4.4 Extreme Points and 1-randomised Policies; 4.5 A Parameter-Free Model; Part III Optimisation; Chapter 5 Determinants; 5.1 Introduction; 5.2 Optimality at Hamiltonian Cycles; 5.2.1 Unperturbed Case; 5.2.2 Perturbed Case; Chapter 6 Traces; 6.1 Introduction; 6.2 Optimality at Hamiltonian Cycles; 6.2.1 Unperturbed Case; 6.2.2 Perturbed Case; Part IV Algorithms; Chapter 7 Linear Programming Based Algorithms; 7.1 Introduction; 7.2 Branch and Fix Method; 7.3 An Algorithm that Implements the Branch and FixMethod; 7.4 Wedge Constraints. 7.5 The Wedged-MIP heuristicChapter 8 Interior Point and Cross-Entropy Algorithms; 8.1 Introduction; 8.2 Interior Point Method Algorithm; 8.3 Cross-Entropy Algorithm; 8.4 Open Algorithmic Problems; Part V Geometric Approaches; Chapter 9 Self-similar Structure and Hamiltonicity; 9.1 Introduction; 9.2 Preliminaries; 9.3 Self-similar Multifilar Structure; 9.4 Self-similarity and Hamiltonicity; Chapter 10 Graph Enumeration; 10.1 Introduction; 10.2 Subdivision-equivalent Edges; 10.3 Enumerating Cubic Bridge Graphs; References; Index; |
| Titelhinweis |
Buchausg. u.d.T.: ‡Hamiltonian cycle problem and Markov chains |
| ISBN |
ISBN 978-1-4614-3232-6 |
| ISBN 1-280-78766-X ebk |
| ISBN 978-1-280-78766-9 MyiLibrary |
| Klassifikation |
KJMD |
| KJT |
| BUS049000 |
| *90-02 |
| 90B50 |
| 60J20 |
| 05C99 |
| 90C27 |
| 90C35 |
| 658.40301 |
| 515.39 |
| HD30.23 |
| Kurzbeschreibung |
Illustrative Graphs -- Intriguing Properties -- Markov Chains -- Markov Decision Processes -- Determinants -- Traces -- Linear Programming Based Algorithms -- Interior Point and Cross-Entropy Algorithms -- Self-similar Structure and Hamiltonicity -- Graph Enumeration |
| 2. Kurzbeschreibung |
This research monograph summarizes a line of research that maps certain classical problems of discrete mathematics and operations research - such as the Hamiltonian cycle and the Travelling Salesman problems - into convex domains where continuum analysis can be carried out. Arguably, the inherent difficulty of these, now classical, problems stems precisely from the discrete nature of domains in which these problems are posed. The convexification of domains underpinning the reported results is achieved by assigning probabilistic interpretation to key elements of the original deterministic problems. In particular, approaches summarized here build on a technique that embeds Hamiltonian Cycle and Traveling Salesman problems in a structured singularly perturbed Markov decision process. The unifying idea is to interpret subgraphs traced out by deterministic policies (including Hamiltonian cycles, if any) as extreme points of a convex polyhedron in a space filled with randomized policies. The above, innovative, approach has now evolved to the point where there are many, both theoretical and algorithmic, results that exploit the nexus between graph theoretic structures and both probabilistic and algebraic entities of related Markov chains. The latter include moments of first return times, limiting frequencies of visits to nodes, or the spectra of certain matrices traditionally associated with the analysis of Markov chains. However, these results and algorithms are dispersed over more than fifteen research papers appearing in journals catering to disparate audiences such as: MOR, Random Structures and Algorithms, SIAM J. on Discrete Mathematics, Optimization, J. of Mathematical Analysis and Applications and some others. Furthermore, because of the evolution of this topic and specific orientation of these journals, the published manuscripts are often written in a very terse manner and use disparate notation. As such it is difficult for new researchers to make use of the many advances reported in these papers. Hence the main purpose of this book is to present a concise and yet, well written, synthesis of the majority of the theoretical and algorithmic results obtained so far. In addition the book will discuss numerous open questions and problems that arise from this body of work and which are yet to be fully solved. The authors believe that their approach casts the Hamiltonian Cycle and Traveling Salesman problems in a mathematical framework that permits ... |
| 1. Schlagwortkette |
Hamilton-Kreis |
| Travelling-salesman-Problem |
| Diskreter Markov-Prozess |
| ANZEIGE DER KETTE |
Hamilton-Kreis -- Travelling-salesman-Problem -- Diskreter Markov-Prozess |
| SWB-Titel-Idn |
365271721 |
| Signatur |
Springer E-Book |
| Bemerkungen |
Elektronischer Volltext - Campuslizenz |
| Elektronische Adresse |
$uhttp://dx.doi.org/10.1007/978-1-4614-3232-6 |
| Internetseite / Link |
Volltext |
| Siehe auch |
Volltext |
| Siehe auch |
Inhaltstext |
