Atlas home || Conferences | Abstracts | about Atlas

Computational Techniques and Applications Conference and Workshops - CTAC99
September 20-24, 1999
The Australian National University
Canberra, ACT, Australia

Organizers
Mike Osborne, Bob Gingold, Steve Roberts, David Harrar II, Thanh Tran, Bob Anderssen, Henry Gardner, Markus Hegland, Lutz Grosz

View Abstracts
Conference Homepage

Hamiltonian Cycles and Markov Chains
by
Jerzy Filar
University of South Australia

HAMILTONIAN CYCLES AND MARKOV CHAINS

HAMILTONIAN CYCLES AND MARKOV CHAINS

Jerzy A. Filar1

Abstract

In this presentation we describe new characterizations of the Hamiltonian cycles of a directed graph, and a new LP-relaxation of the Travelling Salesman Problem. Our results are obtained via an embedding of these combinatorial optimization problems in suitably perturbed controlled Markov chains. This embedding lends probabilistic interpretation to many of the quantities of interest, which in turn lead naturally to the introduction of a quadratic entropy-like function. If the feasible region of the above mentioned LP-relaxation is denoted by X, it can be shown that the extreme points of X can be ordered according to the value of an appropriately constructed linear function L(.). The Hamiltonian cycles correspond to precisely those extreme points of X which take on the second smallest possible value of L(.). Furthermore, they are the minimizers of the top left element of the fundamental matrices of the Markov chains corresponding to deterministic policies of the perturbed controlled Markov chains. We report on the initial computational experiments based on the above approaches.

Footnotes:

1Centre for Industrial and Applicable Mathematics, School of Mathematics, University of South Australia

Date received: June 30, 1999

Copyright © 1999 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadk-12.