Hamiltonian Cycle Problem and Markov Chains

Vivek S. Borkar

ISBN 10: 1461432316 / ISBN 13: 9781461432319

Editore: Springer New York, Springer US Apr 2012, 2012

Riguardo questo articolo

Neuware -This research monograph summarizes a line of research that mapscertain classical problems of discrete mathematics and operationsresearch - such as the Hamiltonian Cycle and the Travelling SalesmanProblems - into convex domains where continuum analysis can be carriedout. Arguably, the inherent difficulty of these, now classical,problems stems precisely from the discrete nature of domains in whichthese problems are posed. The convexification of domains underpinningthese results is achieved by assigning probabilistic interpretation tokey elements of the original deterministic problems. In particular,the approaches summarized here build on a technique that embedsHamiltonian Cycle and Travelling Salesman Problems in a structuredsingularly perturbed Markov decision process. The unifying idea is tointerpret subgraphs traced out by deterministic policies (includingHamiltonian 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 thereare many, both theoretical and algorithmic, results that exploit thenexus between graph theoretic structures and both probabilistic andalgebraic entities of related Markov chains. The latter includemoments of first return times, limiting frequencies of visits tonodes, or the spectra of certain matrices traditionally associatedwith the analysis of Markov chains. However, these results andalgorithms are dispersed over many research papers appearing injournals catering to disparate audiences. As a result, the publishedmanuscripts are often written in a very terse manner and use disparatenotation, thereby making it difficult for new researchers to make use of the many reported advances.Hence the main purpose of this book is to present a concise and yeteasily accessible synthesis of the majority of the theoretical andalgorithmicresults obtained so far. In addition, the book discussesnumerous open questions and problems that arise from this body of workand which are yet to be fully solved. The approach casts theHamiltonian Cycle Problem in a mathematical framework that permitsanalytical concepts and techniques, not used hitherto in this context,to be brought to bear to further clarify both the underlyingdifficulty of NP-completeness of this problem and the relativeexceptionality of truly difficult instances. Finally, the material isarranged in such a manner that the introductory chapters require verylittle mathematical background and discuss instances of graphs with interesting structures that motivated a lot of the research in this topic.More difficult results are introduced later and are illustrated withnumerous examples.Springer Verlag GmbH, Tiergartenstr. 17, 69121 Heidelberg 216 pp. Englisch.

Codice articolo 9781461432319

Dati bibliografici

• Titolo: Hamiltonian Cycle Problem and Markov Chains
• Editore: Springer New York, Springer US Apr 2012
• Data di pubblicazione: 2012
• Lingua: Inglese
• ISBN 10: 1461432316
• ISBN 13: 9781461432319
• Rilegatura: Buch
• Condizione: Neu
• Dimensioni: 241 L x 160 A x 17 P (millimetri) 241 millimetri di larghezza per 160 millimetri di altezza per 17 millimetri di profondità
• Peso: 494 grammi

Descrizione articolo

Riassunto

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 these results is achieved by assigning probabilistic interpretation to key elements of the original deterministic problems. In particular, the approaches summarized here build on a technique that embeds Hamiltonian Cycle and Travelling 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 many research papers appearing in journals catering to disparate audiences. As a result, the published manuscripts are often written in a very terse manner and use disparate notation, thereby making it difficult for new researchers to make use of the many reported advances.

Hence the main purpose of this book is to present a concise and yet easily accessible synthesis of the majority of the theoretical and algorithmic results obtained so far. In addition, the book discusses numerous open questions and problems that arise from this body of work and which are yet to be fully solved. The approach casts the Hamiltonian Cycle Problem in a mathematical framework that permits analytical concepts and techniques, not used hitherto in this context, to be brought to bear to further clarify both the underlying difficulty of NP-completeness of this problem and the relative exceptionality of truly difficult instances. Finally, the material is arranged in such a manner that the introductory chapters require very little mathematical background and discuss instances of graphs with interesting structures that motivated a lot of the research in this topic. More difficult results are introduced later and are illustrated with numerous examples.

Dalla quarta di copertina

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 analytical concepts and techniques, not used hitherto in their context, to be brought to bear to further clarify both the underlying difficulty of NP-completeness of these problems and the relative exceptionality of truly difficult instances.

Finally, the material is arranged in such a manner that the introductory chapters require very little mathematical background and discuss instances of graphs with interesting structures that motivated a lot of the research in this topic. More difficult results are introduced later but, unlike the research manuscripts where they were originally proved, are illustrated with numerous examples.