Improved Approximation for the Maximum Duo-Preservation String Mapping Problem

DOI10.1007/978-3-662-44753-6_2zbMath1382.68345OpenAlexW2241163761MaRDI QIDQ5265098

Samuli Leppänen, Adam Kurpisz, Nicolas Boria, Monaldo Mastrolilli

Publication date: 22 July 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-44753-6_2

zbMATH Keywords

linear programmingpolynomial approximationconfiguration LPmin common string partition problemmax duo-preserving string mapping problem

Mathematics Subject Classification ID

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

Related Items (5)

Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ 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: Improved Approximation for the Maximum Duo-Preservation String Mapping Problem