标题：Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem
作者：Jiang, Haitao; Ma, Jingjing; Luan, Junfeng; Zhu, Daming
作者机构：[Jiang, Haitao; Ma, Jingjing; Luan, Junfeng; Zhu, Daming] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.
会议名称：21st International Computing and Combinatorics Conference (COCOON)
会议日期：AUG 04-06, 2015
来源：COMPUTING AND COMBINATORICS
摘要：Scaffold filling is an interesting combinatorial optimization problem from genome sequencing. The one-sided scaffold filling problem can be stated as: given an incomplete scaffold with some genes missing and a reference scaffold, the purpose is to insert the missing genes back into the incomplete scaffold(called "filling the scaffold"), such that the number of common adjacencies between the filled scaffold and the reference scaffold is maximized. This problem is NP-hard for genome with duplicated genes, and can be approximated within 1.25 by a very complicated combinatorial method. In this paper, we firstly improve the approximation factor to 6/5 by not-oblivious local search; then we show that this problem is MAX-SNP-complete.