The Resource Hamiltonian cycle problem and markov chains, Vivek S. Borkar...[et al.], (electronic resource)

Hamiltonian cycle problem and markov chains, Vivek S. Borkar...[et al.], (electronic resource)

Label
Hamiltonian cycle problem and markov chains
Title
Hamiltonian cycle problem and markov chains
Statement of responsibility
Vivek S. Borkar...[et al.]
Contributor
Provider
Subject
Genre
Language
eng
Summary
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
Member of
Cataloging source
GW5XE
Image bit depth
0
LC call number
QA614.83
LC item number
.H36 2012
Literary form
non fiction
Nature of contents
dictionaries
http://library.link/vocab/relatedWorkOrContributorName
  • SpringerLink
  • Borkar, Vivek S
Series statement
International Series in Operations Research & Management Science,
Series volume
171
http://library.link/vocab/subjectName
  • Hamiltonian systems
  • Markov processes
  • MATHEMATICS / Differential Equations / General
  • Economics/Management Science
  • Operations Research/Decision Theory
  • Operations Research, Management Science
  • Optimization
  • Probability Theory and Stochastic Processes
  • Hamiltonian systems
  • Markov processes
  • Science économique
  • Affaires
Label
Hamiltonian cycle problem and markov chains, Vivek S. Borkar...[et al.], (electronic resource)
Instantiates
Publication
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
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
Dimensions
unknown
Extent
1 online resource (xiv, 201 p.)
File format
multiple file formats
Form of item
  • online
  • electronic
Isbn
9781461432326
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
  • 9786613698056
  • 10.1007/978-1-4614-3232-6
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
Stock number
369805
System control number
  • (OCoLC)792942621
  • (OCoLC)ocn792942621
Label
Hamiltonian cycle problem and markov chains, Vivek S. Borkar...[et al.], (electronic resource)
Publication
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
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
Dimensions
unknown
Extent
1 online resource (xiv, 201 p.)
File format
multiple file formats
Form of item
  • online
  • electronic
Isbn
9781461432326
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
c
Other control number
  • 9786613698056
  • 10.1007/978-1-4614-3232-6
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
Stock number
369805
System control number
  • (OCoLC)792942621
  • (OCoLC)ocn792942621

Library Locations

  • African Studies LibraryBorrow it
    771 Commonwealth Avenue, 6th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Alumni Medical LibraryBorrow it
    72 East Concord Street, Boston, MA, 02118, US
    42.336388 -71.072393
  • Astronomy LibraryBorrow it
    725 Commonwealth Avenue, 6th Floor, Boston, MA, 02445, US
    42.350259 -71.105717
  • Fineman and Pappas Law LibrariesBorrow it
    765 Commonwealth Avenue, Boston, MA, 02215, US
    42.350979 -71.107023
  • Frederick S. Pardee Management LibraryBorrow it
    595 Commonwealth Avenue, Boston, MA, 02215, US
    42.349626 -71.099547
  • Howard Gotlieb Archival Research CenterBorrow it
    771 Commonwealth Avenue, 5th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Mugar Memorial LibraryBorrow it
    771 Commonwealth Avenue, Boston, MA, 02215, US
    42.350723 -71.108227
  • Music LibraryBorrow it
    771 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Pikering Educational Resources LibraryBorrow it
    2 Silber Way, Boston, MA, 02215, US
    42.349804 -71.101425
  • School of Theology LibraryBorrow it
    745 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350494 -71.107235
  • Science & Engineering LibraryBorrow it
    38 Cummington Mall, Boston, MA, 02215, US
    42.348472 -71.102257
  • Stone Science LibraryBorrow it
    675 Commonwealth Avenue, Boston, MA, 02445, US
    42.350103 -71.103784
Processing Feedback ...