SMS scnews item created by Zhou Zhang at Mon 15 Apr 2013 1533
Type: Seminar
Distribution: World
Expiry: 6 May 2013
Calendar1: 18 Apr 2013 1200-1300
CalLoc1: AGR Carslaw 829
Auth: zhangou@como.maths.usyd.edu.au

# 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/


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