| Time: Nov 26, 10:00-11:00 (Taipei Time) |
| Speaker: Kuo-Chin Chen (Hon-Hai Research Institute) |
| Title: An adaptive algorithm for the exact Euclidean traveling salesman problem with quadratic improvement |
|
| Abstract: |
| de Berg [An ETH-tight exact algorithm for Euclidean TSP, 2018] solved the Euclidean traveling salesman problem (ETSP) with n points in R^d by deriving a divide-and-conquer algorithm with a running time of 2^O(n^(1-1/d)). Their algorithm is near optimal because algorithms with a time complexity of less than 2^o(n^(1-1/d)) do not exist unless ETH fails. This result leaves very little room for further improving ETSP algorithms. However, in this paper, we make a nontrivial modification to de Berg et al.’s algorithm that results in a quadratic speedup. Our technical contribution is an adaptive strategy that can balance the size of the divided subproblems with the complexity of merging them in each iteration. |
|
| Video: https://www.youtube.com/watch?v=s6tQLbxdBHg&list=PLRv5VlacpLeHNob2T12NK3DNNpGbtJ_M5&index=26 |
