Approximation algorithms for sorting by bounded singleton moves

DOI10.1016/J.TCS.2022.03.011OpenAlexW4221056238MaRDI QIDQ2143142FDOQ2143142

Authors: Shengjun Xie, Haodi Feng, Haitao Jiang, Daming Zhu 

Publication date: 31 May 2022

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

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

Recommendations

• An approximation algorithm for sorting by bounded singleton moves
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Sorting by short block-moves
• A 14/11-approximation algorithm for sorting by short block-moves
• A \((1+\varepsilon)\)-approximation algorithm for sorting by short block-moves

zbMATH Keywords

permutationapproximation algorithmbounded singleton move

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Sorting a bridge hand
• Sorting by Transpositions
• A 14/11-approximation algorithm for sorting by short block-moves
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Sorting by bounded block-moves
• Sorting by short block-moves
• On sorting by 3-bounded transpositions
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves

This page was built for publication: Approximation algorithms for sorting by bounded singleton moves

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