License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.10
URN: urn:nbn:de:0030-drops-73458
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7345/
Go to the corresponding LIPIcs Volume Portal

Dudek, Bartlomiej ; Gawrychowski, Pawel ; Ostropolski-Nalewaja, Piotr

A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem

pdf-format:
LIPIcs-CPM-2017-10.pdf (0.6 MB)

Abstract

In the Maximum Duo-Preservation 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 well-studied 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 Duo-Preservation String Mapping is APX-hard. After a series of improvements, Brubach [WABI 2016] showed a polynomial-time 3.25-approximation algorithm. Our main contribution is that, for any eps>0, there exists a polynomial-time (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.67-approximation in quadratic time.

BibTeX - Entry

@InProceedings{dudek_et_al:LIPIcs:2017:7345,
  author =	{Bartlomiej Dudek and Pawel Gawrychowski and Piotr Ostropolski-Nalewaja},
  title =	{{A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7345},
  URN =		{urn:nbn:de:0030-drops-73458},
  doi =		{10.4230/LIPIcs.CPM.2017.10},
  annote =	{Keywords: approximation scheme, minimum common string partition, local search}
}

Keywords: approximation scheme, minimum common string partition, local search
Collection: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 30.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI