DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2016.11

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

Authors: Nicolas Boria, Gianpiero Cabodi, Paolo Camurati, Marco Palena, Paolo Pasini, and Stefano Quer

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

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.

Cite as

Nicolas Boria, Gianpiero Cabodi, Paolo Camurati, Marco Palena, Paolo Pasini, and Stefano Quer. A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boria_et_al:LIPIcs.CPM.2016.11,
  author =	{Boria, Nicolas and Cabodi, Gianpiero and Camurati, Paolo and Palena, Marco and Pasini, Paolo and Quer, Stefano},
  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 =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.11},
  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}
}

@InProceedings{boria_et_al:LIPIcs.CPM.2016.11,
  author =	{Boria, Nicolas and Cabodi, Gianpiero and Camurati, Paolo and Palena, Marco and Pasini, Paolo and Quer, Stefano},
  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 =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.11},
  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}
}

Search Results

Documents authored by Camurati, Paolo

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

Abstract

Cite as

Thanks for your feedback!

Could not send message