An Improved Approximation Algorithm for the Complementary Maximum Strip Recovery Problem
Full Text: 1-s2.0-S0022000011001206-main.pdf
Given two genomic maps and each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both and such that the resultant subsequences, denoted as ⁎ and ⁎ , can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown to be NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved -approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a local amortization with a re-weighting scheme.
Citation
G. Lin, R. Goebel, Z. Li, L. Wang. "An Improved Approximation Algorithm for the Complementary Maximum Strip Recovery Problem". Journal of Computer and Systems Sciences, 78(3), pp 720-730, May 2012.| Keywords: | Maximal strip recovery, Approximation algorithm, Local amortized analysis, Re-weighting scheme |
| Category: | In Journal |
| Web Links: | Elsevier |
| DOI |
BibTeX
@article{Lin+al:12,
author = {Guohui Lin and Randy Goebel and Zhong Li and Lusheng Wang},
title = {An Improved Approximation Algorithm for the Complementary Maximum
Strip Recovery Problem},
Volume = "78",
Number = "3",
Pages = {720-730},
journal = {Journal of Computer and Systems Sciences},
year = 2012,
}Last Updated: February 13, 2020Submitted by Sabina P
