9781601980892 (electronic)
IR
EN-53502
انگلیسی
IR
Controlled Markov chains, graphs and hamiltonicity
[Book]
/ Jerzy A. Filar
Hanover, Mass.
: Now Publishers,
, c2007.
1 electronic text (p. [77]-162 ill. (some col.)) , digital file.
(Foundations and trends in stochastic systems, 1551-3092
; v. 1, issue 2, p. 77-162)
Title from PDF (viewed on March 26, 2009).
Electronic
Includes bibliographical references (p. 158-162).
The topic 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. Numerous open questions and problems are described in the presentation.
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.
This manuscript summarizes a line of research that maps certain classical problems of discrete mathematics -- such as the Hamiltonian Cycle and the Traveling 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.
Abstract -- 1. Embedding of a graph in a Markov decision process -- 2. Analysis in the policy space -- 3. Analysis in the frequency space - 4. Spectral properties, spin-offs, and speculation -- Acknowledgments -- References.
Foundations and trends in stochastic systems (Online), 1551-3092 ; v. 1, issue 2, p. 77-162
Markov processes
Hamiltonian graph theory
E-BOOK
Filar, Jerzy A., 1949-
ایران
9781601980885.pdf
عادی
عادی
9781601980885.pdf
متن
old catalog
e
BL
1
a
Y
