An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves

DOI10.1007/978-3-319-13075-0_39zbMath1432.68578OpenAlexW2278556741MaRDI QIDQ2942654

Haodi Feng, Daming Zhu, Haitao Jiang

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_39

Mathematics Subject Classification ID

Searching and sorting (68P10) Permutations, words, matrices (05A05) Approximation algorithms (68W25)

Related Items (4)

Approximation algorithms for sorting permutations by length-weighted short rearrangements ⋮ Approximation algorithms for sorting by bounded singleton moves ⋮ Length-weighted \(\lambda\)-rearrangement distance ⋮ Sorting a permutation by best short swaps

Cites Work

• A 14/11-approximation algorithm for sorting by short block-moves
• Sorting by bounded block-moves
• Sorting by short block-moves
• On sorting by 3-bounded transpositions
• Sorting by Transpositions Is Difficult
• Sorting by Transpositions
• On Representatives of Subsets
• Sorting a bridge hand

This page was built for publication: An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves