An approximate A(*) algorithm and its application to the SCS problem

In this paper we deal with algorithm A(*) and its application to the problem of finding the shortest common supersequence of a set of sequences. A(*) is a powerful search algorithm which may be used to carry out concurrently the construction of a network and the solution of a shortest path problem on it. We prove a general approximation property of A(*) which, by building a smaller network, allows us to find a solution with a given approximation ratio. This is particularly useful when dealing with large instances of some problem. We apply this approach to the solution of the shortest common supersequence problem and show its effectiveness. (C) 2002 Elsevier Science B.V. All rights reserved