Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
This work addresses computational efficiency for permutation problems, offering incremental improvements in space-time tradeoffs for algorithms in combinatorial optimization.
The paper tackles the space-time tradeoff for permutation problems, specifically improving the bound for the Traveling Salesperson Problem to S·T ≤ 3.7493^N, which surpasses a previously identified optimal barrier of 3.9271^N. This result is achieved by introducing a new parameter called chain efficiency and constructing set systems with high efficiency.
We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem that solves $N$-vertex instances using space $S$ and time $T$ where $S\cdot T \leq 3.7493^{N}$. This improves a previous work by Koivisto and Parviainen [SODA'10] where $S\cdot T \leq 3.9271^N$, and overcomes a barrier they identified, as their bound was shown to be optimal within their framework. To get our results, we introduce a new parameter of a set system that we call the chain efficiency. This relates the number of maximal chains contained in the set system with the cardinality of the system. We show that set systems of high efficiency imply efficient space-time tradeoffs for permutation problems, and give constructions of set systems with high chain efficiency, disproving a conjecture by Johnson, Leader and Russel [Comb. Probab. Comput.'15].