String Comparison: Hardness and Approximations

String comparison is a fundamental problem in computer science, with applications in text processing, data compression or computational biology. In the general edit distance problem, we are given two strings A and B and a set of string operations (e.g., delete, insert or change a character, substring move or a substring reversal) and the task is to find the minimum number of operations needed to convert A to B. Closely related is the Minimum Common String Partition problem (MCSP): we are given two strings , and we wish to partition them into the same collection of substrings, minimizing the number of the substrings in the partition. In the talk we will show that already a very restricted version of the {MCSP} is NP-hard, and even hard to approximate. We will also deal with a natural greedy algorithm for the problem.

Joint work with Marek Chrobak, Avraham Goldstein, Jiri Sgall and Jie Zheng.

Speaker: Petr Kolman is an Assistant Professor at the Dept. of Applied Mathematics, Charles University in Prague, Czech Republic.

Formerly also at University of California, Riverside, Computer Science Dept. (2003-2004), Heinz Nixdorf Institute, University of Paderborn, Germany (1999-2000) and the Supercomputing Center, Czech Technical University, Prague, Czech Republic (1995-1998). Petr Kolman obtained an MSc.(1995) and a PhD. (1998) degree in Computer Science at the Faculty of Mathematics and Physics, Charles University in Prague.