LIPIcs.CPM.2016.11.pdf
- Filesize: 427 kB
- 8 pages
Document
A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem
Authors
-
Part of:
Volume:
27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-27
Cite As Get BibTex
Nicolas Boria, Gianpiero Cabodi, Paolo Camurati, Marco Palena, Paolo Pasini, and Stefano Quer. A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CPM.2016.11
Abstract
This paper presents a simple 7/2-approximation algorithm for the Maximum Duo-Preservation String Mapping (MPSM) problem. This problem is complementary to the classical and well studied min common string partition problem (MCSP), that computes the minimal edit distance between two strings when the only operation allowed is to shift blocks of characters. The algorithm improves on the previously best-known 4-approximation algorithm by computing a simple local optimum.
Subject Classification
Keywords
- Polynomial approximation
- Max Duo-Preservation String Mapping Problem
- Min Common String Partition Problem
- Local Search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- S. Beretta, M. Castelli, and R. Dondi. Parameterized Tractability of the Maximum-Duo Preservation String Mapping Problem. ArXiv e-prints, December 2015. URL: http://arxiv.org/abs/1512.03220.
- N. Boria, A. Kurpisz, S. Leppänen, and M. Mastrolilli. Improved approximation for the maximum duo-preservation string mapping problem. In Dan Brown and Burkhard Morgenstern, editors, Algorithms in Bioinformatics, volume 8701 of Lecture Notes in Computer Science, pages 14-25. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44753-6_2.
- L. Bulteau, G. Fertin, C. Komusiewicz, and I. Rusu. A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications. In WABI, pages 244-258, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40453-5_19.
- L. Bulteau and C. Komusiewicz. Minimum common string partition parameterized by partition size is fixed-parameter tractable. In SODA, pages 102-121, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.8.
- J. Chen, I.A. Kanj, and W. Jia. Vertex Cover: Further Observations and Further Improvements. In Peter Widmayer, Gabriele Neyer, and Stephan Eidenbenz, editors, WG, volume 1665 of Lecture Notes in Computer Science, pages 313-324. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-46784-X_30.
- 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(0):1-11, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.02.017.
- X. Chen, J. Zheng, Z. Fu, P. Nan, Y. Zhong, S. Lonardi, and T. Jiang. Assignment of Orthologous Genes via Genome Rearrangement. Transactions on Computational Biology and Bioinformatics, 2(4):302-315, 2005. URL: http://dx.doi.org/10.1145/1100863.1100950.
- M. Chrobak, P. Kolman, and J. Sgall. The Greedy Algorithm for the Minimum Common String Partition Problem. In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, and Dana Ron, editors, APPROX-RANDOM, volume 3122 of Lecture Notes in Computer Science, pages 84-95. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27821-4_8.
- G. Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. ACM Transactions on Algorithms, 3(1), 2007. URL: http://dx.doi.org/10.1145/1219944.1219947.
- P. Damaschke. Minimum Common String Partition Parameterized. In Keith A. Crandall and Jens Lagergren, editors, WABI, volume 5251 of Lecture Notes in Computer Science, pages 87-98. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-87361-7_8.
-
R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 1999. 530 pp.
-
M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco, CA, 1979.
-
A. Goldstein, P. Kolman, and J. Zheng. Minimum Common String Partition Problem: Hardness and Approximations. In Rudolf Fleischer and Gerhard Trippen, editors, ISAAC, volume 3341 of Lecture Notes in Computer Science, pages 484-495. Springer, 2004.
- H. Jiang, B. Zhu, D. Zhu, and H. Zhu. Minimum common string partition revisited. Journal of Combinatorial Optimization, 23(4):519-527, 2012. URL: http://dx.doi.org/10.1007/s10878-010-9370-2.
- P. Kolman and T. Walen. Approximating reversal distance for strings with bounded number of duplicates. Discrete Applied Mathematics, 155(3):327-336, 2007. URL: http://dx.doi.org/10.1016/j.dam.2006.05.011.
- P. Kolman and T. Walen. Reversal Distance for Strings with Duplicates: Linear Time Approximation using Hitting Set. Electronic Journal of Combinatorics, 14(1), 2007. URL: http://www.combinatorics.org/Volume_14/Abstracts/v14i1r50.html.
- C. Lund and M. Yannakakis. The Approximation of Maximum Subgraph Problems. In Andrzej Lingas, Rolf G. Karlsson, and Svante Carlsson, editors, ICALP, volume 700 of Lecture Notes in Computer Science, pages 40-51. Springer, 1993. URL: http://dx.doi.org/10.1007/3-540-56939-1_60.
- K.M. Swenson, M. Marron, J.V. Earnest-DeYoung, and B.M.E. Moret. Approximating the true evolutionary distance between two genomes. ACM Journal of Experimental Algorithmics, 12, 2008. URL: http://dx.doi.org/10.1145/1227161.1402297.