Tackling the Minimal Superpermutation Problem

MaRDI QIDQ6254100zbMATH OpenFDO

Authors Robin Houston

Publication date 21 August 2014

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 $su{m}_{i=1}^{n}i!$. The conjecture had been verified for $nleq5$. 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.

This page was built for publication: Tackling the Minimal Superpermutation Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6254100)