Dudek, Bartlomiej ;
Gawrychowski, Pawel ;
OstropolskiNalewaja, Piotr
A Family of Approximation Algorithms for the Maximum DuoPreservation String Mapping Problem
Abstract
In the Maximum DuoPreservation String Mapping problem we are given two strings and wish to map the letters of the former to the letters of the latter as to maximise the number of duos. A duo is a pair of consecutive letters that is mapped to a pair of consecutive letters in the same order. This is complementary to the wellstudied Minimum Common String Partition problem, where the goal is to partition the former string into blocks that can be permuted and concatenated to obtain the latter string.
Maximum DuoPreservation String Mapping is APXhard. After a series of improvements, Brubach [WABI 2016] showed a polynomialtime 3.25approximation algorithm. Our main contribution is that, for any eps>0, there exists a polynomialtime (2+eps)approximation algorithm. Similarly to a previous solution by Boria et al. [CPM 2016], our algorithm uses the local search technique. However, this is used only after a certain preliminary greedy procedure, which gives us more structure and makes a more general local search possible. We complement this with a specialised version of the algorithm that achieves 2.67approximation in quadratic time.
BibTeX  Entry
@InProceedings{dudek_et_al:LIPIcs:2017:7345,
author = {Bartlomiej Dudek and Pawel Gawrychowski and Piotr OstropolskiNalewaja},
title = {{A Family of Approximation Algorithms for the Maximum DuoPreservation String Mapping Problem}},
booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
pages = {10:110:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770392},
ISSN = {18688969},
year = {2017},
volume = {78},
editor = {Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7345},
URN = {urn:nbn:de:0030drops73458},
doi = {10.4230/LIPIcs.CPM.2017.10},
annote = {Keywords: approximation scheme, minimum common string partition, local search}
}
2017
Keywords: 

approximation scheme, minimum common string partition, local search 
Seminar: 

28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Issue date: 

2017 
Date of publication: 

2017 