Improved approximation for the maximum duo-preservation string mapping problem

DOI10.1007/978-3-662-44753-6_2MaRDI QIDQ5265098zbMATHOpenAlexFDO

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

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)

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

Cited in

(11)

• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Further improvement in approximating the maximum duo-preservation string mapping problem
• A family of approximation algorithms for the maximum duo-preservation string mapping problem
• Solving the maximum duo-preservation string mapping problem with linear programming
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *
• Approximating weighted duo-preservation in comparative genomics

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)