标题：A (1.408+epsilon)-Approximation Algorithm for Sorting Unsigned Genomes by Reciprocal Translocations
作者：Jiang, Haitao; Wang, Lusheng; Zhu, Binhai; Zhu, Daming
作者机构：[Jiang, Haitao; Zhu, Daming] Shandong Univ, Sch Comp Sci & Technol, Jinan 250100, Peoples R China.; [Wang, Lusheng] City Univ Hong Kong, Dept Comp S 更多
会议名称：8th International Frontiers of Algorithmics Workshop (FAW)
会议日期：JUN 28-30, 2014
来源：FRONTIERS IN ALGORITHMICS, FAW 2014
摘要：Sorting genomes by translocations is a classic combinatorial problem in genome rearrangements. The translocation distance for signed genomes can be computed exactly in polynomial time, but for unsigned genomes the problem becomes NP-Hard and the current best approximation ratio is 1.5+epsilon. In this paper, we investigate the problem of sorting unsigned genomes by translocations. Firstly, we propose a tighter lower bound of the optimal solution by analyzing some special sub-permutations; then, by exploiting the two well-known algorithms for approximating the maximum independent set on graphs with a bounded degree and for set packing with sets of bounded size, we devise a new polynomial-time approximation algorithm, improving the approximation ratio to 1.408+epsilon, where epsilon = O(1/log n).