Markov chains, Hamiltonian cycles and volumes of convex bodies |
| |
Authors: | Vivek S Borkar Jerzy A Filar |
| |
Institution: | 1. School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai, 400005, India 2. School of Computer Science, Engineering and Mathematics, Flinders University, Bedford Park, Adelaide, SA, 5042, Australia
|
| |
Abstract: | In this note the Hamiltonian cycle problem is mapped into an infinite horizon discounted cost constrained Markov decision problem. The occupation measure based linear polytope associated with this control problem defines a convex set which either strictly contains or is equal to another convex set, depending on whether the underlying graph has a Hamiltonian cycle or not. This allows us to distinguish Hamiltonian graphs from non-Hamiltonian graphs by comparing volumes of two convex sets. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|