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: https://drops.dagstuhl.de/opus/volltexte/2016/6087/
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: |
|
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 | |
| Seminar: | 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 27.06.2016 |
