@inproceedings{7567c15ac94748048f0f23ddcb778fda,
title = "A (1.4 + ∈)-Approximation algorithm for the 2-max-duo problem",
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 ? ≤ 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 + ∈)-Approximation was claimed, for any > 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.",
keywords = "Approximation algorithm, Duo-preservation string mapping, Independent set, String partition",
author = "Yao Xu and Yong Chen and Guohui Lin and Tian Liu and Taibo Luo and Peng Zhang",
year = "2017",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2017.66",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Takeshi Tokuyama and Yoshio Okamoto",
booktitle = "28th International Symposium on Algorithms and Computation, ISAAC 2017",
address = "Germany",
note = "28th International Symposium on Algorithms and Computation, ISAAC 2017 ; Conference date: 09-12-2017 Through 22-12-2017",
}