Document Open Access Logo

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

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2017.66.pdf
  • Filesize: 0.74 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Approximation algorithm
  • duo-preservation string mapping
  • string partition
  • independent set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.ISAAC.2017.66

Author Details

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

References

  1. S. Beretta, M. Castelli, and R. Dondi. Parameterized tractability of the maximum-duo preservation string mapping problem. Theoretical Computer Science, 646:16-25, 2016. Google Scholar
  2. P. Berman and T. Fujito. On approximation properties of the independent set problem for low degree graphs. Theory of Computing Systems, 32:115-132, 1999. Google Scholar
  3. P. Berman and M. Karpinski. On some tighter inapproximability results. In Proceedings of the of 26th International Colloquium on Automata, Languages and Programming (ICALP'99), pages 200-209, 1999. Google Scholar
  4. N. Boria, G. Cabodi, P. Camurati, M. Palena, P. Pasini, and S. Quer. A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem. In Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), volume 54 of LIPIcs, pages 11:1-11:8, 2016. Google Scholar
  5. N. Boria, A. Kurpisz, S. Leppänen, and M. Mastrolilli. Improved approximation for the maximum duo-preservation string mapping problem. In Proceedings of the 14th International Workshop on Algorithms in Bioinformatics (WABI 2014), volume 8701 of LNBI, pages 14-25, 2014. Google Scholar
  6. B. Brubach. Further improvement in approximating the maximum duo-preservation string mapping problem. In Proceedings of the 16th International Workshop on Algorithms in Bioinformatics (WABI 2016), volume 9838 of LNBI, pages 52-64, 2016. Google Scholar
  7. L. Bulteau, G. Fertin, C. Komusiewicz, and I. Rusu. A fixed-parameter algorithm for minimum common string partition with few duplications. In Proceedings of the 13th International Workshop on Algorithms in Bioinformatics (WABI 2013), volume 8126 of LNBI, pages 244-258, 2013. Google Scholar
  8. L. Bulteau and C. Komusiewicz. Minimum common string partition parameterized by partition size is fixed-parameter tractable. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 102-121, 2014. Google Scholar
  9. W. Chen, Z. Chen, N. F. Samatova, L. Peng, J. Wang, and M. Tang. Solving the maximum duo-preservation string mapping problem with linear programming. Theoretical Computer Science, 530:1-11, 2014. Google Scholar
  10. X. Chen, J. Zheng, Z. Fu, P. Nan, Y. Zhong, S. Lonardi, and T. Jiang. Assignment of orthologous genes via genome rearrangement. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2:302-315, 2005. Google Scholar
  11. M. Chrobak, P. Kolman, and J. Sgall. The greedy algorithm for the minimum common string partition problem. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2004) and the 8th International Workshop on Randomization and Computation (RANDOM 2004), volume 3122 of LNCS, pages 84-95, 2004. Google Scholar
  12. G. Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. ACM Transactions on Algorithms, 3:2:1-2:19, 2007. Google Scholar
  13. P. Damaschke. Minimum common string partition parameterized. In Proceedings of the 8th International Workshop on Algorithms in Bioinformatics (WABI 2008), volume 5251 of LNBI, pages 87-98, 2008. Google Scholar
  14. B. Dudek, P. Gawrychowski, and P. Ostropolski-Nalewaja. A family of approximation algorithms for the maximum duo-preservation string mapping problem. arXiv, 1702.02405, 2017. Google Scholar
  15. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, San Francisco, 1979. Google Scholar
  16. A. Goldstein, P. Kolman, and J. Zheng. Minimum common string partition problem: Hardness and approximations. In Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC 2004), volume 3341 of LNCS, pages 484-495, 2004. Google Scholar
  17. H. Jiang, B. Zhu, D. Zhu, and H. Zhu. Minimum common string partition revisited. Journal of Combinatorial Optimization, 23:519-527, 2012. Google Scholar
  18. P. Kolman and T. Waleń. Reversal distance for strings with duplicates: Linear time approximation using hitting set. In Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA 2006), volume 4368 of LNCS, pages 279-289, 2006. Google Scholar
  19. P. Kolman and T. Waleń. Approximating reversal distance for strings with bounded number of duplicates. Discrete Applied Mathematics, 155:327-336, 2007. Google Scholar
  20. Y. Xu, Y. Chen, T. Luo, and G. Lin. A local search 2.917-approximation algorithm for duo-preservation string mapping. arXiv, 1702.01877, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact