In this talk, we introduce a certain polytope arising from embedding the Hamiltonian cycle problem in a discounted Markov decision process. The Hamiltonian cycle problem can be reduced to finding particular extreme points of a certain polytope associated with the input graph. This polytope is a subset of the space of discounted occupational measures. We characterize the feasible bases of the polytope for a general input graph G, and determine the expected numbers of different types of feasible bases when the underlying graph is random. We utilize these results to demonstrate that augmenting certain additional constraints to reduce the polyhedral domain, can eliminate a large number of feasible bases which do not correspond to Hamiltonian cycles. Finally, we develop a random walk algorithm on the feasible bases of the reduced polytope and present some numerical results. We conclude this talk with a conjecture on the feasible bases of the reduced polytope.
About Maths Colloquium
The Mathematics Colloquium is directed at students and academics working in the fields of pure and applied mathematics, and statistics.
We aim to present expository lectures that appeal to our wide audience.
Information for speakers
Information for speakers
Maths colloquia are usually held on Mondays, from 2pm to 3pm, in various locations at St Lucia.
Presentations are 50 minutes, plus five minutes for questions and discussion.
Available facilities include:
- computer
- data projector
- chalkboard or whiteboard
To avoid technical difficulties on the day, please contact us in advance of your presentation to discuss your requirements.