{"id":"arxiv/2604.05645","url":"https://arxiv.org/abs/2604.05645","tags":["cs.DS","math.CO"],"score":0,"title":"Improved space-time tradeoff for TSP via extremal set systems","domain":"cs.DS","source":"arxiv","authors":["Justin Dallant","László Kozma"],"reviews":0,"subject":"cs.DS","summary":"The traveling salesman problem (TSP) is a cornerstone of combinatorial optimization and has deeply influenced the development of algorithmic techniques in both exact and approximate settings. Yet, improving on the decades-old bounds for solving TSP exactly remains elusive: the dynamic program of Bellman, Held, and Karp from 1962 uses $2^{n+O(\\log{n})}$ time and space, and the divide-and-conquer approach of Gurevich and Shelah from 1987 uses $4^{n + O(\\log^2{n})}$ time and polynomial space. A straightforward combination of the two algorithms trades off $T^{n+o(n)}$ time and $S^{n+o(n)}$ space…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-07","reactions":{}}