Block Sorting Is APX-Hard

DOI10.1007/978-3-319-18173-8_28zbMath1459.68079OpenAlexW1134184770MaRDI QIDQ2947036

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

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

Cites Work

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

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