2026-07-22T22:18:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8212 2024-03-06T10:41:54Z ddc:004 open_access

A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem Xu, Yao Chen, Yong Lin, Guohui Liu, Tian Luo, Taibo Zhang, Peng Approximation algorithm duo-preservation string mapping string partition independent set 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 \Delta \le 6(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yao Xu and Yong Chen and Guohui Lin and Tian Liu and Taibo Luo and Peng Zhang 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.66 urn:nbn:de:0030-drops-82120 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.66 eng https://creativecommons.org/licenses/by/3.0/legalcode