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

DOI10.1016/J.TCS.2012.03.019MaRDI QIDQ441865zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

permutationapproximation algorithmshort block-move

Mathematics Subject Classification ID

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

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

Cites work

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

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)