Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913015057612800 |
|---|---|
| author | Ameli, Afrouz Jabal Nederlof, Jesper Wang, Shengzhe |
| author_facet | Ameli, Afrouz Jabal Nederlof, Jesper Wang, Shengzhe |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05661 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics Ameli, Afrouz Jabal Nederlof, Jesper Wang, Shengzhe Data Structures and Algorithms Discrete Mathematics Combinatorics 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]. |
| title | Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2604.05661 |