SMS scnews item created by Zhou Zhang at Wed 12 Oct 2011 1410
Type: Seminar
Modified: Wed 12 Oct 2011 1424; Mon 17 Oct 2011 1122
Distribution: World
Expiry: 27 Oct 2011
Calendar1: 21 Oct 2011 1430-1530
CalLoc1: Carslaw 175
Auth: zhangou@bari.maths.usyd.edu.au

# Joint Colloquium: Filar -- The Hamiltonian Cycle Problem, Markov Chains and Optimization

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.

-----------------------------------------------------


If you are registered you may mark the scnews item as read.
School members may try to .