A (1+)-approximation algorithm for sorting by short block-moves

DOI10.1016/J.TCS.2012.03.019zbMATH Open1245.68145OpenAlexW1973005012MaRDI QIDQ441865FDOQ441865

Authors: Haitao Jiang, Daming Zhu, Binhai Zhu 

Publication date: 8 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.019

Recommendations

• A 14/11-approximation algorithm for sorting by short block-moves
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Sorting by short block-moves
• APPROXIMATE BLOCK SORTING
• (1+ε)-Approximation of Sorting by Reversals and Transpositions

zbMATH Keywords

permutationapproximation algorithmshort block-move

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Searching and sorting (68P10) Approximation algorithms (68W25)

Cites Work

• Sorting a bridge hand
• Sorting by Transpositions
• Sorting by bounded block-moves
• Sorting by short block-moves
• On sorting by 3-bounded transpositions

Cited In (10)

• APPROXIMATE BLOCK SORTING
• Length-weighted \(\lambda\)-rearrangement distance
• Approximation algorithms for sorting by bounded singleton moves
• Sorting a permutation by best short swaps
• A quadratic time 2-approximation algorithm for block sorting
• Sorting by short block-moves
• Approximation algorithms for sorting permutations by length-weighted short rearrangements
• A 14/11-approximation algorithm for sorting by short block-moves
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Block Sorting Is APX-Hard

This page was built for publication: A \((1+\varepsilon)\)-approximation algorithm for sorting by short block-moves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441865)