HackerPapers

arXiv:1408.5108math.CO

Tackling the Minimal Superpermutation Problem

Robin Houston

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
5 pages
Journal reference
DOI
Subjects
math.COCombinatorics cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 2 comments across 2 threads, from Oct 2016 to Oct 2018.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Superpermutations 1 comment

    • The technique may be different, but the results seem to be identical to what you get from the standard method e.g. described in Section 2 of http://www.njohnston.ca/wp-content/uploads/2013/03/minimal_s...; or section 1 of https://arxiv.org/pdf/1408.5108.pdf; or as implemented by…

      robinhoustonView on HNParent context

  2. Image unshredding using a TSP solver 1 comment

    • Not so long ago, we’d say “That’s an NP-complete problem” with the implication that it was hopeless to expect an efficient solution. Now (to exaggerate a little) it’s more like a sign that there probably is an efficient solution using some powerful solver. LKH is a lovely piece…

      robinhoustonView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.