%0 Journal Article %A A.S. Rebaï and M. Elloumi %D 2007 %J International Journal of Mathematical and Computational Sciences %B World Academy of Science, Engineering and Technology %I Open Science Index 12, 2007 %T Approximation Algorithm for the Shortest Approximate Common Superstring Problem %U https://publications.waset.org/pdf/14792 %V 12 %X The Shortest Approximate Common Superstring (SACS) problem is : Given a set of strings f={w1, w2, ... , wn}, where no wi is an approximate substring of wj, i ≠ j, find a shortest string Sa, such that, every string of f is an approximate substring of Sa. When the number of the strings n>2, the SACS problem becomes NP-complete. In this paper, we present a greedy approximation SACS algorithm. Our algorithm is a 1/2-approximation for the SACS problem. It is of complexity O(n2*(l2+log(n))) in computing time, where n is the number of the strings and l is the length of a string. Our SACS algorithm is based on computation of the Length of the Approximate Longest Overlap (LALO). %P 609 - 614