环型二元序列的赋权对换排序问题

环型二元序列的赋权对换排序问题

亓兴勤¹, 曹静², 张晨³

1.山东大学威海分校数学系, 山东威海 264209; 2. 燕山大学理学院, 河北秦皇岛 066004;3. 山东大学威海分校国有资产管理处, 山东威海 264209

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 亓兴勤

Sorting circular binary strings with length weighted transpositions

QI Xing-qin¹,CAO Jing²,ZHANG Chen³

1. Department of Mathematics, Shandong University at Weihai, Weihai264209;2. College of Science, Yanshan University, Qinhuangdao 066004;3. StateOwned Assets Supervision and Administration Faculty, Shandong Univerisity at Weihai

Received:1900-01-01 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: QI Xing-qin

摘要/Abstract

摘要： 研究了环型二元序列的赋权对换排序问题。定义一个长度为l的对换的费用是f(l)=lα,0≤α<1,对环型二元序列的赋权对换排序问题给出了一个O(logn)近似算法,其中n是环型二元序列的长度。

关键词: 环型二元序列, 近似算法 , 对换

Abstract: The problem of sorting circular binary strings with length-weighted transpositions was considered, i.e. the cost of a transposition is f(l)=lα,0≤α<1, where l is the length of the transposition. An O(logn)approximation algorithm is given for sorting a circular binary string with the minimum cost, where n is the length of the circular string. The result has direct applications in computational biology in the field of comparative genomics.

Key words: approximation algorithm , transposition, circular binary string

中图分类号:

TP301

亓兴勤,曹静,张晨 . 环型二元序列的赋权对换排序问题[J]. J4, 2007, 42(12): 46-48 .

QI Xing-qin,CAO Jing,ZHANG Chen . Sorting circular binary strings with length weighted transpositions[J]. J4, 2007, 42(12): 46-48 .

参考文献

相关文章 9

[1]	蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.
[2]	杨朝霞 . 超图嵌入带权重圈的一个2-近似算法[J]. J4, 2008, 43(8): 11-13 .
[3]	杨振光,李曙光,王秀红 . 工件尺寸不同的并行机批调度问题[J]. J4, 2007, 42(4): 63-66 .
[4]	戴珍香,李曙光,亓兴勤 . 波分复用星形单跳网中3信道的传输调度问题[J]. J4, 2007, 42(2): 46-50 .
[5]	李曙光,白淑岩,何志红,亓兴勤 . 圈中t-区间的k-染色问题[J]. J4, 2006, 41(6): 40-42 .
[6]	李曙光,杨振光,何志红 . 多纤波分复用链网与环网中的利润极大化问题[J]. J4, 2006, 41(5): 7-11 .
[7]	王继强, . 一类median问题的近似算法研究[J]. J4, 2006, 41(4): 1-03 .
[8]	李曙光,亓兴勤,何志红 . 环网络中的呼叫接纳控制[J]. J4, 2006, 41(4): 15-19 .
[9]	亓兴勤,何志红,赵洪銮 . 二元序列的赋权对换排序问题[J]. J4, 2006, 41(1): 82-85 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed