REVIEW 2 cited by
Tackling the Minimal Superpermutation Problem
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
A superpermutation on $n$ symbols is a string that contains each of the $n!$ permutations of the $n$ symbols as a contiguous substring. The shortest superpermutation on $n$ symbols was conjectured to have length $\sum_{i=1}^n i!$. The conjecture had been verified for $n \leq 5$. We disprove it by exhibiting an explicit counterexample for $n=6$. This counterexample was found by encoding the problem as an instance of the (asymmetric) Traveling Salesman Problem, and searching for a solution using a powerful heuristic solver.
Forward citations
Cited by 2 Pith papers
-
Supertrees
The minimum size of a contiguous k-universal d-ary plane tree is exactly d^{k-1}+k-1; the noncontiguous variants have minimum sizes between roughly k log_2 k and k^{(1/2) log_2 k}.
-
Superpermutation matrices
Defines superpermutation matrices, reduces their row/column minimization to a universal word problem for quotient classes in S_n, and proves the ratio of the resulting upper and lower bounds tends to 2 as n grows.
Discussion (0). Continue with ORCID to comment.