MS9 M INIMUM S ORTING BY R EVERSALS

       
• I NSTANCE : Permutation of the numbers 1 to n .
• S OLUTION : A sequence of reversals of intervals such that is the identity permutation. A reversal of an interval [i,j] is the permutation .
• M EASURE : The number of reversals, i.e., t .

• Good News: Approximable within 7/4 [ 31 ].
• 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 [ 32 ].