The Hamiltonian Cycle Problem and Some Challenging Non-Convex Programs

摘要

We consider the famous Hamiltonian cycle problem (HCP) embedded in a Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of state-action frequencies induced by the MDP’s stationary policies.