A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem

DOI10.4230/LIPICS.CPM.2016.11MaRDI QIDQ5369545zbMATH OpenOpenAlexFDO

Authors Nicolas Boria, G. Cabodi, Paolo Camurati, Marco Palena, P. Pasini, S. Quer

Publication date 17 October 2017

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

zbMATH Keywords

local searchmax duo-preservation string mapping problemmin common string partition problempolynomial approximation

Mathematics Subject Classification ID

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

Recommendations

• Further improvement in approximating the maximum duo-preservation string mapping problem
• A family of approximation algorithms for the maximum duo-preservation string mapping problem
• Improved approximation for the maximum duo-preservation string mapping problem
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

Cited in

(14)

• Alphabet indexing for approximating features of symbols
• Further improvement in approximating the maximum duo-preservation string mapping problem
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• Approximating weighted duo-preservation in comparative genomics
• Solving the maximum duo-preservation string mapping problem with linear programming
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Corrigendum to: ``Parameterized tractability of the maximum-duo preservation string mapping problem.
• A family of approximation algorithms for 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-Max-Duo Problem
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• Improved approximation for the maximum duo-preservation string mapping problem
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *

This page was built for publication: A 7/2-approximation algorithm 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 Q5369545)