An improved approximation algorithm for the complementary maximal strip recovery problem

DOI10.1016/j.jcss.2011.10.014zbMath1244.68087OpenAlexW2042644003MaRDI QIDQ439932

Zhong Li, Randy Goebel, Lusheng Wang, Guo-Hui Lin

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.10.014

zbMATH Keywords

approximation algorithmlocal amortized analysismaximal strip recoveryre-weighting scheme

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items (9)

The complexity of finding common partitions of genomes with predefined block sizes ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ Tractability and approximability of maximal strip recovery ⋮ A linear kernel for the complementary maximal strip recovery problem ⋮ A 42k Kernel for the Complementary Maximal Strip Recovery Problem ⋮ An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem ⋮ A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics

Cites Work

• Exact and approximation algorithms for the complementary maximal strip recovery problem
• On recovering syntenic blocks from comparative maps
• Inapproximability of Maximal Strip Recovery: II
• Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms
• Scheduling Split Intervals

This page was built for publication: An improved approximation algorithm for the complementary maximal strip recovery problem