Optimal Chain Density, Entropy, and Space-Time Tradeoffs for the TSP

Jul 16, 2026

We study an extremal set-system question over [n] balancing the number of sets and the number of full (maximal) chains. The problem is connected to the space–time complexity of Bellman–Held–Karp style dynamic programming for permutation problems such as the traveling salesman (TSP). For a feasible set system with normalized size S and chain density D, the framework yields a space–time product γ=S^2/D. This work establishes an essentially optimal bound γ≈3.1819, and derives near-optimal chain densities across feasible sizes, closing the gap between prior bounds. It further uses an information–entropy reformulation to obtain tight primal–dual bounds and an application to Boolean lattice fibres.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages27

Reading Time1 h 8 min

Abstract

Introduction

TSP and dynamic programming tradeoffs

Linear extensions and poset downsets

Set systems, maximal chains, and the general framework

Reformulation as an information–entropy tradeoff

Implications for space–time product bounds

arXiv :2607 . 1 13 1 1v 1 [ cs .DS] 13 Jul 2026 Optimal chain density, entropy, and space-time tradeoffs for the TSP Alexandr Andoni 1 , Justin Dallant 2 , László Kozma 2 , and Hantao Yu 1 1 Columbia University 2 Dresden University of Technology Abstract We nearly settle a natural extremal question about set systems over [n]: the tradeoff between the size (number of sets) and the number of full chains. This question was initially raised by Johnson, Leader, and Russell [Combin. Probab. Comp., 2015] as a counterpart to Sperner-type results in combinatorics. Recently, a framework introduced by Ameli, Nederlof, and Wang, and independently by Dallant and Kozma [FOCS 2026] linked this question to the space- and time-complexity of Bellman-Held-Karp-style dynamic programming algorithms for permutation problems such as the traveling salesman (TSP) . Precisely, they showed that a space-time product γn+o(n) is feasible for the TSP, whenever a set system of (normalized) size S and chain density D exists, with γ = S2 /D. In this paper we show an essentially optimal bound of γ ≈ 3.1819 for this quantity, closing the gap between the previous best lower and upper bounds of γ ≥ 3.015 and γ ≤ 3.572 respectively. This implies a TSP algorithm with space-time product O(3 .1819n ) for input size n, as well as a limit to further improvements in this broad framework. More generally, we can obtain close to optimal values D for any feasible value S , effectively settling the question of the number of full chains at every size. The crucial step towards our results is casting the extremal combinatorics question as an information vs. entropy tradeoff involving two random variables. This reformulation exactly captures the optimal tradeoff for the combinatorial problem, leading to a framework in which primal-dual certificates can be derived, proving rigorous upper and lower bounds on γ . We also give a further application of our techniques, improving a bound of Duffus, Sands, and Winkler on the minimum size of fibres in the Boolean lattice. 1 Introduction The traveling salesman problem (TSP) is one of the cornerstones of combinatorial optimization and has served as a proving ground for many of the algorithmic techniques invented in the past decades, whether exact, approximate, or heuristic, e.g., see [Sch05 , ABCC06 , Coo11 , TV24] . Yet, despite significant effort, the fastest algorithm for solving TSP exactly, in the worst case, remains the Bellman-Held-Karp [HK62 , Bel62] dynamic program with running time and space O∗ (2n ) . When the space budget is bounded by a polynomial, the fastest known algorithm is the 1 Email: [andoni@cs.columbia.edu](andoni@cs.columbia.edu). , [hantao.yu@columbia.edu](hantao.yu@columbia.edu) [2](2 Email: justin.dallant@tu-dresden.de)[ Email: justin.dallant@tu-dresden.de](2 Email: justin.dallant@tu-dresden.de), laszlo.kozma@tu-dresden.de Gurevich-Shelah [GS87] divide-and-conquer with running time O∗ (4n ) .1 A folklore combination of the two methods results in a running time O∗(Tn ) and space O∗(Sn ) with T · S = 4, for various values of 1 ≤ S ≤ 2 (e.g., see [FK10 , § 10]) . While the two extremes (T = 2 and T = 4) of this tradeoff have resisted improvement for several decades now, in a surprising breakthrough in 2010, Koivisto and Parviainen [KP10] improved the tradeoff at intermediate points, in particular, to T · S ≈ 3.93, for T ≈ 2.7. Their result builds on the classical dynamic programming (DP) approach of Bellman, Held, and Karp, but partitions the space of possible solutions (all permutations of the input) into sets of permutations that are linear extensions of certain partial orders. This allows searching each subset separately, reusing space between successive searches. Informally, the number of linear extensions determines what fraction of the solution space is covered by one search, and thus the number of repetitions that are needed. The number of downsets (poset ideals) exactly corres

FAQs

What extremal problem does the paper nearly settle?

It studies the tradeoff, for set systems over [n], between the number of sets and the number of full/maximal chains.

How is the set-system tradeoff connected to TSP algorithms?

A recent framework links the existence of set systems (with size S and chain density D) to the space–time product of Bellman–Held–Karp style dynamic programming for the TSP.

What is the main result about the space–time product γ?

The paper proves an essentially optimal bound γ≈3.1819 for the quantity γ=S^2/D, closing the gap between earlier lower and upper bounds.

Jul 16, 2026

Upload by Clementine