Local Search techniques for the Maximum Duo-Preservation String Mapping Problem

1 avril 19

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.