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.
