GREEDY SHORTEST SUPERSTRING WITH DELAYED RANDOM CHOICE

Abstract

The shortest superstring problem for a given set of strings is to find a string of minimum length such that each input string is a substring of the resulting string. This problem is known to be NP-complete. A simple and popular approximation algorithm for this problem is GREEDY, which at each step merges a pair of strings that have maximum overlap. If more than one pair have maximum overlap, it takes a pair in random. In this paper, we modify GREEDY such that instead of taking a pair in random, it takes the pair for which the overlap in the next step is maximum. We analyze our algorithm and compare it with GREEDY for different types of input. We implement both the algorithms and the experimental results show that our algorithm can outperform GREEDY substantially in many cases, and in general our algorithm is same or better than GREEDY.