.png){kind=icon}
返回
A 14/11-approximation algorithm for sorting by short block-moves
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-010-4131-5.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Block-move is one of the popular operations for genome rearrangement. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. Heath and Vergara investigated the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation and devised a 4/3-approximation algorithm. In this paper, we present a new 14/11-approximation algorithm for this problem. Firstly, we devise an exact polynomial time algorithm for sorting a special kind of sub-permutations called umbrella; then we split the permutation into a series of related umbrellas and sort them greedily. We obtain a new lower bound of the short block-move distance by exploiting the properties of five kinds of sub-permutations. After some complicated analysis, we prove that the approximation ratio of the new algorithm is at most 14/11.
Keyword:
short block-move
approximation
algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
7.6
论文数:
4.9K
被引数:
8.9K
机构
引用论文
.png){kind=icon}
Repair of Full Thickness Defect of the Nose Using an Expanded Forehead Flap and a Glabellar Flap
PREAI
分享收藏
查看更多内容