Spending a large part of 30 years on one problem requires dedication, but Flinders mathematician Professor Jerzy Filar hopes a useful solution is in sight.
“The Hamiltonian Cycle Problem (or HCP) is one of those classical problems in math which researchers around the world keep coming back to,” says Strategic Professor of Mathematics and Statistics Professor Filar.
“Now our research team has developed an elegant algorithm and software to produce reliable solutions to, literally, millions of instances; including some that are challenging for most competing algorithms,”
The challenging HCP graph theory problem is one of a number research projects forming the basis of Flinders’ Mathematical Sciences Laboratory, a recently created research hub within the School of Computer Science, Engineering and Mathematics.
With funding from an ARC Discovery grant, the Flinders research team – including Professor Filar, Associate Professor Vladimir Ejov, Dr Michael Haythorpe, Serguei Rossomakhine and other students – along with eminent national and international collaborators have developed numerous approaches to analysing and solving the HCP.
This includes their flagship Snakes and Ladders Heuristic solution, which will not only improve understanding of HCP but also help to solve difficult instances of the closely related travelling salesman problem that has challenged mathematicians and computer scientists since, at least, 1940s.
The logistics and transport industries will benefit from solutions to the travelling salesman problem, which poses the question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
“The great thing about mathematical discoveries is that they don’t have a use-by date,” says Professor Filar.
The Flinders Mathematical Science Laboratory’s focus is on addressing problems that have challenged top mathematicians, engineers and computer scientists to focus on breakthrough science and frontier technologies to build and transform Australian industries – in line with the Australian Research Council’s research priority.
A group of eminent advisers are steering growth of the lab, which works with other Flinders research units which use math research, including the Faculty of Medicine, Nursing and Health Sciences, School of the Environment and National Centre for Groundwater Research and Training.
The lab’s advisory group comprises leading mathematicians Flinders Emeritus Professor Michael Barber, Professor Joe Gani (ANU) – along with Professor Terence Tao (University of California, Los Angeles), Professor Tony Guttmann and Professor Peter Taylor (both University of Melbourne), Professor Nalini Joshi (University of Sydney) who will meet during the 59th Annual Meeting of the Australian Mathematical Society at Flinders University on 28 September.
During the AustMS conference (28 September to 1 October), world-renowned mathematician and Australia’s only Fields Medal winner, Flinders alumnus Professor Tao will give a free public lecture at Adelaide Town Hall on 28 September. For more information go to the link here.