Directed graphs, Hamiltonicity and doubly stochastic matrices
Directed graphs, Hamiltonicity and doubly stochastic matrices
复制标题
DOI：
10.1002/rsa.v25:4
复制
发表时间：
2004-12
影响因子：
1
通讯作者：
V. Borkar;V. Ejov;J. Filar
中科院分区：
文献类型：
--
作者：
V. Borkar;V. Ejov;J. Filar
我们考虑奇异摄动（受控）马尔可夫链中的Hamilton圈问题。我们还考虑了由相同策略诱导的马尔可夫链的基本矩阵的（1，1）-项组成的过程的平稳策略空间上的泛函。特别是，我们专注于这些政策的子集，诱导双随机概率转移矩阵，我们称之为“双随机政策。”我们表明，当扰动参数e是足够小的最小值，这个功能的空间上的双随机政策达到非常接近的哈密顿循环，只要图是哈密顿的。我们还推导出精确的分析表达式的基本矩阵的元素，使自己的概率解释，以及渐近表达式的第一个对角元素，为各种确定性的政策，特别感兴趣的，包括那些对应于汉密尔顿周期。© 2004 Wiley Periodicals，Inc.随机结构算法，2004这项工作得到了澳大利亚研究理事会资助的支持。
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 e 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, for a variety of deterministic policies that are of special interest, including those that correspond to Hamiltonian cycles. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004This work is supported by Australian Research Council Grant.