A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem
Boria, Nicolas, Gianpiero Cabodi, Paolo Enrico Camurati, Marco Palena, Paolo Pasini, Stefano Quer · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
This paper presents a simple 7/2-approximation algorithm for the Maximum Duo-Preservation String Mapping (MPSM) problem. This problem is complementary to the classical and well studied min common string partition problem (MCSP), that computes the minimal edit distance between two strings when the only operation allowed is to shift blocks of characters. The algorithm improves on the previously best-known 4-approximation algorithm by computing a simple local optimum.