Next: MAXIMUM COMPATIBLE BINARY CONSTRAINT Up: Miscellaneous Previous: MINIMUM PARTITION OF RECTANGLE Index

### MINIMUM SORTING BY REVERSALS

- INSTANCE: Permutation of the numbers 1 to n.

- SOLUTION: A sequence of reversals of intervals such that is the identity permutation. A reversal of an interval [i,j] is the permutation .

- MEASURE: The number of reversals, i.e., t.

- Good News: Approximable within 3/2 [105].

- Bad News: Not approximable within 1.0008 [70].

- Comment: MINIMUM SORTING BY TRANSPOSITIONS, the problem where transpositions are used instead of reversals, is approximable within 3/2. A transposition where i<j<k is the permutation [49].