- 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 [113].*Bad News:*Not approximable within 1.0008 [76].*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 [52].