Markov chains, Hamiltonian cycles and volumes of convex bodies

Markov chains, Hamiltonian cycles and volumes of convex bodies

0.00 Avg rating0 Votes
Article ID: iaor20131926
Volume: 55
Issue: 3
Start Page Number: 633
End Page Number: 639
Publication Date: Mar 2013
Journal: Journal of Global Optimization
Authors: ,
Keywords: programming: markov decision
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.

Reviews

Required fields are marked *. Your email address will not be published.