A factor-two approximation for shortest common superstring

Gives a deterministic polynomial-time algorithm constructing a common superstring of length at most twice the optimum for every finite family of explicitly represented strings. The running time is polynomial in the full encoded input length, including symbol labels. (Lean)

Manuscript

A Polynomial-Time 2-Approximation for Shortest Common Superstring

September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026}

We give a deterministic algorithm that, for every finite family of explicitly represented ordinary strings, outputs a common superstring of length at most twice the optimum in time polynomial in the total encoded input size, including symbol labels. The guarantee applies to the algorithm constructed here, not the classical maximum-overlap Greedy procedure.

Result 128 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.