GTA Seminar: Burton -- Untangling Knots Using Combinatorial Optimisation

Speaker: Benjamin Burton (Queensland)

http://www.maths.uq.edu.au/~bab/

Time: Thursday, April 18, 12NOON--1PM

Room: Carslaw 829, AGR

Lunch: after the talk. The reservation at Law Annex 
Cafe is at 1:10PM. 

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

Title: Untangling Knots Using Combinatorial Optimisation

Abstract: unknot recognition is the algorithmic problem 
of determining whether a knot (i.e., a closed loop) in 
3-dimensional space can be untangled. It is a major 
unsolved problem as to whether this problem has a fast 
polynomial time solution.  Here we present the first 
conclusive algorithm for unknot recognition which, 
although exponential time in theory, exhibits a clear 
polynomial time behaviour in exhaustive practical 
experiments. The algorithm makes significant use of 
techniques from combinatorial optimisation, and uses 
a branch-and-bound framework with linear programming 
steps. We also introduce the topological software 
package Regina (in which the algorithm was implemented), 
and discuss the relevance of our results to other 
difficult problems in computational topology.

This is joint work with Melih Ozlen. 

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

Seminar website:

http://www.maths.usyd.edu.au/u/SemConf/Geometry/