Further improvement in approximating the maximum duo-preservation string mapping problem

DOI10.1007/978-3-319-43681-4_5MaRDI QIDQ1708415zbMATH OpenOpenAlexFDO

Authors Brian Brubach

Publication date 23 March 2018

Full work available at URL https://doi.org/10.1007/978-3-319-43681-4_5

zbMATH Keywords

string algorithmspolynomial-time approximationmax duo-preservation string mapping problemmin common string partition problem

Mathematics Subject Classification ID

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

Recommendations

• Improved approximation for the maximum duo-preservation string mapping problem
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• 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

(9)

• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *
• 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
• A family of approximation algorithms for the maximum duo-preservation string mapping problem
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• Improved approximation for the maximum duo-preservation string mapping problem
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• Solving the maximum duo-preservation string mapping problem with linear programming

This page was built for publication: Further improvement in approximating 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 Q1708415)