An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem

DOI10.1007/978-3-642-21204-8_9zbMath1329.68292OpenAlexW2294802772MaRDI QIDQ3004655

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

Publication date: 3 June 2011

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21204-8_9

zbMATH Keywords

approximation algorithmmaximal strip recoverysequential amortized analysis

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

Maximal strip recovery problem with gaps: hardness and approximation algorithms

Cites Work

• Exact and approximation algorithms for the complementary maximal strip recovery problem
• An improved approximation algorithm 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