- FR
- EN
lundi 1 avril 2019, 14h, salle P303
Abstract :
Computing distances between complex objects such as strings or graphs is a central issue as its applications range from data compression to clustering and classification. Such distances can be measured in various ways, however the most common measure is the so-called edit distance, which computation results in various combinatorial optimization problems depending on the edit-operations allowed and the cost functions considered.
The MIN COMMON STRING PARTITION is a widely studied problem, that consists in computing the edit distance between two strings, when the only edit operation allowed is to shift a block of characters. We briefly present the state of the art regarding the maximization counterpart of the problem denoted by MAX DUO-PRESERVATION STRING MAPPING, and provide some details on two approximation algorithms for the problem, first a simple 7/2-approximation algorithm based on local search, and then its refinement to a 2+epsilon approximation scheme, the best approximation known to this day.
