Family 128Theoretical computer scienceLeanNot yet digested
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.
Manuscripts in this family · 1
A Polynomial-Time 2-Approximation for Shortest Common Superstring
Sep 24, 2026·paper.pdfLean
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.