Paper Info
Title
Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
Abstract
The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n22n) time. Since then it has been a notorious problem to improve the runtime to O((2−є)n) for some constant є>0. In this work we establish the following progress: If (s× s)-matrices can be multiplied in s2+o(1) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999n) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs. On a high level, our approach is via a new problem called MinHamPair: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MinHamPair based on a new sparse cut-based factorization of the ‘matchings connectivity matrix’, introduced by Cygan et al. [JACM’18].
Year
DOI
Venue
2020
10.1145/3357713.3384264
STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing Chicago IL USA June, 2020
Keywords
DocType
ISSN
Traveling Salesman Problem, Exponential Time algorithms
Conference
0737-8017
ISBN
Citations 
PageRank 
978-1-4503-6979-4
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Jesper Nederlof129424.22