|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Hamiltonian Cycle Problem and Markov Chainsкнига
- Авторы: Borkar Vivek S., Ejov Vladimir, Filar Jerzy A., Nguyen Giang T.
- Год издания: 2012
- Издательство: Springer New York
- Местоположение издательства: New York, N.Y., United States
- ISBN: 978-1-4614-3231-9
- DOI: 10.1007/978-1-4614-3232-6
- Аннотация: 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
- Добавил в систему: Ежов Владимир Владимирович