A Polynomial-Time 2-Approximation for Shortest Common SuperstringResearch Paper
Given a finite collection of strings, the shortest common superstring (SCS) problem asks for a shortest string that contains every member of as a contiguous substring. It is a basic model of sequence assembly (reconstructing a long DNA sequence from overlapping fragments) and of data compression, and it is a standard test problem for…