A 1.375-Approximation Algorithm for Sorting by Transpositions | Zendy

Isaac Elias | Zendy; Tzvika Hartman | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A 1.375-Approximation Algorithm for Sorting by Transpositions

Author(s) -

Isaac Elias,

Tzvika Hartman

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/11557067_17

Subject(s) - transposition (logic) , sorting , permutation (music) , combinatorics , upper and lower bounds , computer science , simple (philosophy) , approximation algorithm , mathematics , algorithm , artificial intelligence , physics , mathematical analysis , philosophy , epistemology , acoustics

Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a ten-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: We improve the lower bound for the transposition diameter of the symmetric group, and determine the exact transposition diameter of 2-permutations and simple permutations.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research