A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

DOI10.4230/LIPIcs.ISAAC.2017.66zbMath1457.68340arXiv1702.06256OpenAlexW3165634411MaRDI QIDQ5136287

Tian Liu, Yao Xu, Peng Zhang, Yong Chen, Guo-Hui Lin, Taibo Luo

Publication date: 25 November 2020

Full work available at URL: https://arxiv.org/abs/1702.06256

zbMATH Keywords

approximation algorithmindependent setduo-preservation string mappingstring partition

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Minimum common string partition revisited
• Approximating reversal distance for strings with bounded number of duplicates
• On approximation properties of the independent set problem for low degree graphs
• Further improvement in approximating the maximum duo-preservation string mapping problem
• Solving the maximum duo-preservation string mapping problem with linear programming
• The string edit distance matching problem with moves
• Improved Approximation for the Maximum Duo-Preservation String Mapping Problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A 7/2-approximation algorithm for the Maximum Duo-Preservation String Mapping Problem
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Algorithms and Computation

This page was built for publication: A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem