标题:Notes on the 6/5-Approximation Algorithm for One-Sided Scaffold Filling
作者:Ma, Jingjing; Jiang, Haitao
通讯作者:Jiang, Haitao
作者机构:[Ma, Jingjing; Jiang, Haitao] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.
会议名称:10th International Frontiers of Algorithmics Workshop (FAW)
会议日期:JUN 30-JUL 02, 2016
来源:Frontiers in Algorithmics, FAW 2016
出版年:2016
卷:9711
页码:145-157
DOI:10.1007/978-3-319-39817-4_15
摘要:We focus on designing algorithm for One-sided Scaffold Filling. Jiang et al. proposed a non-oblivious local search algorithm for this problem recently. We can give an example to show that this algorithm cannot approximate One-sided Scaffold Filling to 6/5. In this paper, we propose a new objective function based local search algorithm for One-sided Scaffold Filling, and give the accurate proof to show that its approximation ratio is 6/5
收录类别:CPCI-S;EI;SCOPUS
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84976629746&doi=10.1007%2f978-3-319-39817-4_15&partnerID=40&md5=171f76d4c966a614d18d227fc74ab63d
TOP