A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem

DOI10.1007/s10878-020-00621-0zbMath1466.90084OpenAlexW2950324999MaRDI QIDQ2023131

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

Publication date: 3 May 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00621-0

zbMATH Keywords

approximation algorithmindependent setduo-preservation string mappingstring partition

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Corrigendum to: ``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
• Approximating the true evolutionary distance between two genomes
• 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-\textsc{Max-Duo} problem