On the hamiltonicity gap and doubly stochastic matrices

Borkar, Vivek S. ; Ejov, Vladimir ; Filar, Jerzy A. (2009) On the hamiltonicity gap and doubly stochastic matrices Random Structures & Algorithms, 34 (4). pp. 502-519. ISSN 1042-9832

Full text not available from this repository.

Official URL: http://onlinelibrary.wiley.com/doi/10.1002/rsa.202...

Related URL: http://dx.doi.org/10.1002/rsa.20237


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 these policies. 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 at a Hamiltonian cycle, provided that the graph is Hamiltonian. We also show that when the graph is non-Hamiltonian, the above minimum is strictly greater than that in a Hamiltonian case. We call the size of this difference the "Hamiltonicity Gap" and derive a conservative lower bound for this gap. Our results imply that the Hamiltonian cycle problem is equivalent to the problem of minimizing the variance of the first hitting time of the home node, over doubly stochastic policies.

Item Type:Article
Source:Copyright of this article belongs to John Wiley and Sons.
Keywords:Hamiltonian Cycle; Controlled Markov Chains; Optimal Policy; Singular Perturbation
ID Code:81472
Deposited On:07 Feb 2012 05:01
Last Modified:07 Feb 2012 05:01

Repository Staff Only: item control page