An Ant Colony Optimization approach to solve the minimum string cover problem

摘要

In this paper, we consider the problem of covering a set of strings S with a set of strings C. C is said to cover S if every string in S can be written as a concatenation of a set of strings which are elements of C. We discuss here three different variants of Ant Colony Optimization (ACO) and propose how we can solve the minimum string cover problem using these techniques. Our simulation results show that ACO based approach gives better solution than the existing approximation algorithm for this problem.