Hamiltonian Cycle Problem and Markov Chains (Record no. 101325)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 05359nam a22005295i 4500 |
| 001 - CONTROL NUMBER | |
| control field | 978-1-4614-3232-6 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | DE-He213 |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20140220083246.0 |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
| fixed length control field | cr nn 008mamaa |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 120420s2012 xxu| s |||| 0|eng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9781461432326 |
| -- | 978-1-4614-3232-6 |
| 024 7# - OTHER STANDARD IDENTIFIER | |
| Standard number or code | 10.1007/978-1-4614-3232-6 |
| Source of number or code | doi |
| 050 #4 - LIBRARY OF CONGRESS CALL NUMBER | |
| Classification number | HD30.23 |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | KJT |
| Source | bicssc |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | KJMD |
| Source | bicssc |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | BUS049000 |
| Source | bisacsh |
| 082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 658.40301 |
| Edition number | 23 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Borkar, Vivek S. |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | Hamiltonian Cycle Problem and Markov Chains |
| Medium | [electronic resource] / |
| Statement of responsibility, etc | by Vivek S. Borkar, Vladimir Ejov, Jerzy A. Filar, Giang T. Nguyen. |
| 264 #1 - | |
| -- | New York, NY : |
| -- | Springer New York, |
| -- | 2012. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | XIV, 201p. 82 illus., 31 illus. in color. |
| Other physical details | online resource. |
| 336 ## - | |
| -- | text |
| -- | txt |
| -- | rdacontent |
| 337 ## - | |
| -- | computer |
| -- | c |
| -- | rdamedia |
| 338 ## - | |
| -- | online resource |
| -- | cr |
| -- | rdacarrier |
| 347 ## - | |
| -- | text file |
| -- | |
| -- | rda |
| 490 1# - SERIES STATEMENT | |
| Series statement | International Series in Operations Research & Management Science, |
| International Standard Serial Number | 0884-8289 ; |
| Volume number/sequential designation | 171 |
| 505 0# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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. |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | 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. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Economics. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Mathematical optimization. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Distribution (Probability theory). |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Economics/Management Science. |
| 650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Operations Research/Decision Theory. |
| 650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Operations Research, Management Science. |
| 650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Optimization. |
| 650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Probability Theory and Stochastic Processes. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Ejov, Vladimir. |
| Relator term | author. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Filar, Jerzy A. |
| Relator term | author. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Nguyen, Giang T. |
| Relator term | author. |
| 710 2# - ADDED ENTRY--CORPORATE NAME | |
| Corporate name or jurisdiction name as entry element | SpringerLink (Online service) |
| 773 0# - HOST ITEM ENTRY | |
| Title | Springer eBooks |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Display text | Printed edition: |
| International Standard Book Number | 9781461432319 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE | |
| Uniform title | International Series in Operations Research & Management Science, |
| -- | 0884-8289 ; |
| Volume number/sequential designation | 171 |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://dx.doi.org/10.1007/978-1-4614-3232-6 |
| 912 ## - | |
| -- | ZDB-2-SBE |
No items available.