%0 Journal Article %1 DBLP:journals/jacm/BlumLTY94 %A Blum, Avrim %A Li, Ming %A Tromp, John %A Yannakakis, Mihalis %D 1994 %J J. ACM %K algorithm shortest_superstring %N 4 %P 630-647 %R 10.1145/179812.179818 %T Linear Approximation of Shortest Superstrings %V 41 %X We consider the following problem: given a collection of strings s1,…, sm, find the shortest string s such that each si appears as a substring (a consecutive block) of s. Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2n), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4n. Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3n. We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.

@article{DBLP:journals/jacm/BlumLTY94, abstract = {We consider the following problem: given a collection of strings s1,…, sm, find the shortest string s such that each si appears as a substring (a consecutive block) of s. Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2n), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4n. Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3n. We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.}, added-at = {2009-11-29T21:33:18.000+0100}, author = {Blum, Avrim and Li, Ming and Tromp, John and Yannakakis, Mihalis}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/2b7828515df0a82ed84f69d690c75e710/ytyoun}, doi = {10.1145/179812.179818}, interhash = {a23085f28a637eb5997aa0f9f5f252ea}, intrahash = {b7828515df0a82ed84f69d690c75e710}, journal = {J. ACM}, keywords = {algorithm shortest_superstring}, number = 4, pages = {630-647}, timestamp = {2016-06-14T14:08:40.000+0200}, title = {Linear Approximation of Shortest Superstrings}, volume = 41, year = 1994 }