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: | Filar Jerzy, Borkar Vivek |
Keywords: | programming: markov decision |
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.