{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibnr4jr72a4ttwfqhmweiiitnhpcxykyh3p72rqn6rgegbhjcostu",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mixhlqa4tcg2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.05645v1",
  "publishedAt": "2026-04-08T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Justin Dallant",
    "László Kozma"
  ],
  "textContent": "**Authors:** Justin Dallant, László Kozma\n\nThe 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 at various points of the curve $ST = 4$. An improvement to this tradeoff when $2 < T < 2\\sqrt{2}$ was found by Koivisto and Parviainen (SODA 2010), yielding a minimum of $ST \\approx 3.93$. Koivisto and Parviainen show their method to be optimal among a broad class of partial-order-based approaches, and to date, no improvement or alternative method has been found. In this paper we give a tradeoff that strictly improves all previous ones for all $2 < T < 4$, achieving a minimum of $ST < 3.572$. A key ingredient is the construction of sparse set systems (hypergraphs) that admit a large number of maximal chains. The existence of such objects is of independent interest in extremal combinatorics, likely to see further applications. Along the way we disprove a combinatorial conjecture of Johnson, Leader, and Russell from 2013, relating it with the optimality of the previous tradeoff schemes for TSP. Our techniques extend to a broad class of permutation problems over arbitrary semirings, yielding improved space-time tradeoffs in these settings as well.",
  "title": "Improved space-time tradeoff for TSP via extremal set systems"
}