DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.66

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

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

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

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

Cite as

Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, and Peng Zhang. A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.ISAAC.2017.66,
  author =	{Xu, Yao and Chen, Yong and Lin, Guohui and Liu, Tian and Luo, Taibo and Zhang, Peng},
  title =	{{A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.66},
  URN =		{urn:nbn:de:0030-drops-82120},
  doi =		{10.4230/LIPIcs.ISAAC.2017.66},
  annote =	{Keywords: Approximation algorithm, duo-preservation string mapping, string partition, independent set}
}

Search Results

Documents authored by Luo, Taibo

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

Abstract

Cite as

Thanks for your feedback!

Could not send message