Block Sorting Is APX-Hard

DOI10.1007/978-3-319-18173-8_28MaRDI QIDQ2947036zbMATH OpenOpenAlexFDO

Authors N. S. Narayanaswamy, Swapnoneel Roy

Publication date 21 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-18173-8_28

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Recommendations

• Block Sorting is Hard
• APPROXIMATE BLOCK SORTING
• Block sorting: a characterization and some heuristics
• Fundamentals of Computation Theory
• A quadratic time 2-approximation algorithm for block sorting
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Optimal narrowing of a block of sortings in optimal time
• A (1+)-approximation algorithm for sorting by short block-moves
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Theory and Applications of Models of Computation

Cites work

• A quadratic time 2-approximation algorithm for block sorting
• Block Sorting is Hard
• Block sorting: a characterization and some heuristics
• Computing and Combinatorics
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Some optimal inapproximability results
• Sorting by Transpositions

Cited in

(4)

• A quadratic time 2-approximation algorithm for block sorting
• Fundamentals of Computation Theory
• Block sorting: a characterization and some heuristics
• Block Sorting is Hard

This page was built for publication: Block Sorting Is APX-Hard

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