本文印刷
全画面プリント
FMSPレクチャーズ
過去の記録 ～04/19｜次回の予定｜今後の予定 04/20～
| 担当者 | 河野俊丈 |
|---|
2013年03月08日(金)
10:30-12:00 数理科学研究科棟(駒場) 056号室
Benjamin Burton 氏 (The University of Queensland, Australia)
Knots, algorithms and linear programming: the quest to solve unknot recognition in polynomial time (ENGLISH)
Benjamin Burton 氏 (The University of Queensland, Australia)
Knots, algorithms and linear programming: the quest to solve unknot recognition in polynomial time (ENGLISH)
[ 講演概要 ]
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.
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.
