Practically efficient algorithms for minimum string cover and minimum common string partition problem

Abstract

Covering and Partitioning problems are very important problems in computer science. Both of them deal with combinatorial structure of the instances. In covering problem the question is whether a certain combinatorial structure covers another. On the other hand the partition problem asks for partitioning a certain combinatorial structure to smaller structures maintaining some constraints. A prominent example of covering problem is Set Cover problem while an important partitioning problem is Integer Partition problem. In these thesis, we are interested in two string related covering and partitioning problem, namely, Minimum String Cover (MSC) problem and Minimum Common String Partition (MSCP) problem. The first one is a covering problem and the second one is the partitioning problem. MSC problems has its application in formal language theory, protein folding and in text compression while MCSP has .its direct application in genome comparison. In this thesis, we are interested in designing efficient and practical algorithms for solving MSC and MCSP problems. As both of them share the NP-hard complexity status and are combinatorial optimization problem, we have applied variants of Ant Colony Optimization (ACO) techniques to solve them. For MCSP we also developed the Mixed Integer Linear Programming formulation. An extensive experiment is carried that compares our result with the state of the art algorithms for these two problems.