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

DOI10.4230/LIPICS.ISAAC.2017.66MaRDI QIDQ5136287zbMATH OpenOpenAlexFDO

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• Algorithms and Computation
• Approximating reversal distance for strings with bounded number of duplicates
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Further improvement in approximating the maximum duo-preservation string mapping problem
• Improved approximation for the maximum duo-preservation string mapping problem
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Minimum common string partition revisited
• On approximation properties of the independent set problem for low degree graphs
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Solving the maximum duo-preservation string mapping problem with linear programming
• The string edit distance matching problem with moves

Cited in

(7)

• scientific article; zbMATH DE number 1226311 (Why is no real title available?)
• 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)