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.2016.11
URN: urn:nbn:de:0030-drops-60875
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6087/
Go to the corresponding LIPIcs Volume Portal

Boria, Nicolas ; Cabodi, Gianpiero ; Camurati, Paolo ; Palena, Marco ; Pasini, Paolo ; Quer, Stefano

A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem

pdf-format:
LIPIcs-CPM-2016-11.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{boria_et_al:LIPIcs:2016:6087,
  author =	{Nicolas Boria and Gianpiero Cabodi and Paolo Camurati and Marco Palena and Paolo Pasini and Stefano Quer},
  title =	{{A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{11:1--11:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Roberto Grossi and Moshe Lewenstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6087},
  URN =		{urn:nbn:de:0030-drops-60875},
  doi =		{10.4230/LIPIcs.CPM.2016.11},
  annote =	{Keywords: Polynomial approximation, Max Duo-Preservation String Mapping Problem, Min Common String Partition Problem, Local Search}
}

Keywords: Polynomial approximation, Max Duo-Preservation String Mapping Problem, Min Common String Partition Problem, Local Search
Collection: 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Issue Date: 2016
Date of publication: 27.06.2016

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