Type: Seminar

Modified: Wed 12 Oct 2011 1424; Mon 17 Oct 2011 1122

Distribution: World

Expiry: 27 Oct 2011

Auth: zhangou@bari.maths.usyd.edu.au

Speaker: Prof. Jerzy A. Filar (Flinders University). Link: http://www.flinders.edu.au/people/jerzy.filar Time: Friday, Oct. 21, 2:30--3:30PM, 2011 Room: Carslaw Lecture Theatre 175, Syd. U. (HERE IS A SMALL CHANGE!!!!) Lunch (COMBINED WITH ALGEBRA SEMINAR LUNCH): meet around 1PM (INSTEAD OF 12:30PM) at the second floor entrance to Carslaw Building and then go to Grandstand (INSTEAD OF the Law School restaurant). ----------------------------------------------------- Title: the Hamiltonian Cycle Problem, Markov Chains and Optimization Abstract: 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 occupational measures induced by the MDP’s stationary policies. In recent years, this approach to the HCP has led to a number of alternative formulations and algorithmic approaches involving researchers from a number of countries. In this lecture we focus on a specific embedding due to E. Feinberg from SUNY at Stony Brook. The latter leads to a suitably constructed parametrized polytope of discounted occupational measures that can be used as a domain where Hamiltonian solutions can be sought. It is known that whenever a given graph possesses Hamiltonian cycles, these correspond to certain extreme points of that polytope. It can be demonstrated that a relatively small number of additional constraints and a judicious choice of the value of the discount parameter can ensure that Hamiltonian solutions are no longer rare among extreme points of this modified sub-polytope of occupational measures. The latter observation leads to a promising random walk algorithm on the extreme points of that sub-polytope. We present a conjecture concerning the algorithmic complexity of this algorithm. In addition, we consider the limiting--parameter free--polyhedral region that can serve as a basis for determining non-Hamiltonicity of cubic graphs. Numerical results indicate that determining non-Hamiltonicity of a great majority of non-Hamiltonian cubic graphs is likely to be a problem of polynomial complexity despite the fact that HCP is known to be NP-complete already for cubic graphs. -----------------------------------------------------