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

DOI10.4230/LIPICS.ISAAC.2017.66zbMATH Open1457.68340arXiv1702.06256OpenAlexW3165634411MaRDI QIDQ5136287FDOQ5136287

Authors: Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, Peng Zhang 

Publication date: 25 November 2020

Abstract: The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. $k$-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most $k$ times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree $Deltale6(k-1)$. In particular, $2$-Max-Duo can then be approximated arbitrarily close to $1.8$ using the state-of-the-art approximation algorithm for the MIS problem. $2$-Max-Duo was proved APX-hard and very recently a $(1.6+epsilon)$-approximation was claimed, for any $epsilon>0$. In this paper, we present a vertex-degree reduction technique, based on which, we show that $2$-Max-Duo can be approximated arbitrarily close to $1.4$.

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

Recommendations

• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• A tight approximation algorithm for problem \(P2\rightarrow D|v=1,c=1|C_{\max }\)
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• Approximate algorithms for the \(P\parallel C_{\max}\) problem
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• scientific article; zbMATH DE number 1559110
• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• scientific article; zbMATH DE number 1304324
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem

zbMATH Keywords

approximation algorithmindependent setduo-preservation string mappingstring partition

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Algorithms and Computation
• Solving the maximum duo-preservation string mapping problem with linear programming
• The string edit distance matching problem with moves
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Minimum common string partition revisited
• Improved approximation 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
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• 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
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem

Cited In (7)

• Title not available (Why is that?)
• 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 tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• Solving the maximum duo-preservation string mapping problem with linear programming

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

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