@article{(Open Science Index):https://publications.waset.org/pdf/14792, title = {Approximation Algorithm for the Shortest Approximate Common Superstring Problem}, author = {A.S. Rebaï and M. Elloumi}, country = {}, institution = {}, abstract = {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).}, journal = {International Journal of Mathematical and Computational Sciences}, volume = {1}, number = {12}, year = {2007}, pages = {609 - 614}, ee = {https://publications.waset.org/pdf/14792}, url = {https://publications.waset.org/vol/12}, bibsource = {https://publications.waset.org/}, issn = {eISSN: 1307-6892}, publisher = {World Academy of Science, Engineering and Technology}, index = {Open Science Index 12, 2007}, }