Directed graphs, Hamiltonicity and doubly stochastic matricesстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 16 июня 2023 г.
Аннотация:We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)‐entry of the fundamental matrices of the Markov chains induced by the same policies. In particular, we focus on the subset of these policies that induce doubly stochastic probability transition matrices, which we refer to as the “doubly stochastic policies.” We show that when the perturbation parameter ϵ is sufficiently small the minimum of this functional over the space of the doubly stochastic policies is attained very close to a Hamiltonian cycle, provided that the graph is Hamiltonian. We also derive precise analytical expressions for the elements of the fundamental matrix that lend themselves to probabilistic interpretation as well as asymptotic expressions for the first diagonal element