A 7/2-approximation algorithm for the Maximum Duo-Preservation String Mapping Problem

DOI10.4230/LIPIcs.CPM.2016.11zbMath1380.68464OpenAlexW2475015781MaRDI QIDQ5369545

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

Publication date: 17 October 2017

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.CPM.2016.11

zbMATH Keywords

polynomial approximationlocal searchmax duo-preservation string mapping problemmin common string partition problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (4)

Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem ⋮ Unnamed Item ⋮ A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

This page was built for publication: A 7/2-approximation algorithm for the Maximum Duo-Preservation String Mapping Problem