2026-07-22T04:53:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6087 2024-03-06T10:37:34Z ddc:004 open_access

A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem Boria, Nicolas Cabodi, Gianpiero Camurati, Paolo Palena, Marco Pasini, Paolo Quer, Stefano Polynomial approximation Max Duo-Preservation String Mapping Problem Min Common String Partition Problem Local Search 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Boria and Gianpiero Cabodi and Paolo Camurati and Marco Palena and Paolo Pasini and Stefano Quer 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.11 urn:nbn:de:0030-drops-60875 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.11 eng https://creativecommons.org/licenses/by/3.0/legalcode