Showing 2026Show all
2 papers · 1 filter
cs.DS2026
Optimal chain density, entropy, and space-time tradeoffs for the TSP
Alexandr Andoni, Justin Dallant, László Kozma +1
We nearly settle a natural extremal question about set systems over : the tradeoff between the {size} (number of sets) and the number of {full chains}. This question was initi…
cs.DS2026
Improved space-time tradeoff for TSP via extremal set systems
Justin Dallant, László Kozma
The traveling salesman problem (TSP) is a cornerstone of combinatorial optimization and has deeply influenced the development of algorithmic techniques in both exact and approximat…