研究集会、講演会等

Knots, algorithms and linear programming: the quest to solve unknot recognition in polynomial time

Benjamin Burton (The University of Queensland, Australia)
2013年3月8日 10:30-12:00
東京大学大学院数理科学研究科056号室

Abstract: In this talk we explore new approaches to the old and difficult computational problem of unknot recognition.  Although the best known algorithms for this problem run in exponential time, there is increasing evidence that a polynomial time solution might be possible.  We outline several promising approaches, in which computational geometry, linear programming and greedy algorithms all play starring roles.  We finish with a new algorithm that combines techniques from topology and combinatorial optimisation, which is the first to exhibit "real world" polynomial time behaviour: although it is still exponential time in theory, exhaustive experimentation shows that this algorithm can solve unknot recognition for "practical" inputs by running just a linear number of linear programs.

This is joint work with Melih Ozlen.