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

DOI10.1016/J.TCS.2014.02.017MaRDI QIDQ2440161zbMATH OpenOpenAlexDBLPWikidataFDO

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

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 programmingapproximation algorithminteger programmingrandomized 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)

Recommendations

• Improved approximation for the maximum duo-preservation string mapping problem
• Further improvement in approximating the maximum duo-preservation string mapping problem
• A 7/2-approximation algorithm 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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1263278 (Why is no real title available?)
• scientific article; zbMATH DE number 1182758 (Why is no real title available?)
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Algorithms and Computation
• Approximating reversal distance for strings with bounded number of duplicates
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Introduction to algorithms
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On approximation of max-vertex-cover
• On dependent randomized rounding algorithms
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Solving Generalized Maximum Dispersion with Linear Programming

Cited in

(9)

• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• A strong designated verifier proxy re-signature scheme for IoT environments
• 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
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2440161)