Improved approximation for the maximum duo-preservation string mapping problem

DOI10.1007/978-3-662-44753-6_2zbMATH Open1382.68345OpenAlexW2241163761MaRDI QIDQ5265098FDOQ5265098

Authors: Nicolas Boria, Adam Kurpisz, Samuli Leppänen, 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

Recommendations

• Solving the maximum duo-preservation string mapping problem with linear programming
• Further improvement in approximating the maximum duo-preservation string mapping problem
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *
• A family of approximation algorithms for the maximum duo-preservation string mapping problem

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)

Cited In (6)

• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Title not available (Why is that?)
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *

This page was built for publication: Improved approximation for the maximum duo-preservation string mapping problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265098)