Solving the maximum duo-preservation string mapping problem with linear programming

DOI10.1016/J.TCS.2014.02.017zbMath1359.68304DBLPjournals/tcs/ChenCSPWT14OpenAlexW2004490284WikidataQ57442833 ScholiaQ57442833MaRDI QIDQ2440161

Wenbin Chen, Lingxi Peng, Maobin Tang, Zhengzhang Chen, Jian-Xiong Wang, Nagiza F. Samatova

Publication date: 27 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.02.017

zbMATH Keywords

linear programminginteger programmingapproximation algorithmrandomized roundingduo-preservation string mappingconstrained maximum induced subgraph problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (8)

Research on QoS service composition based on coevolutionary genetic algorithm ⋮ Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem ⋮ Unnamed Item ⋮ A strong designated verifier proxy re-signature scheme for IoT environments ⋮ A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating reversal distance for strings with bounded number of duplicates
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• On dependent randomized rounding algorithms
• On approximation of max-vertex-cover
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Solving Generalized Maximum Dispersion with Linear Programming
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Algorithms and Computation

This page was built for publication: Solving the maximum duo-preservation string mapping problem with linear programming