Next: MAXIMUM COMPATIBLE BINARY CONSTRAINT
Up: Miscellaneous
Previous: MINIMUM PARTITION OF RECTANGLE
  Index
- 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].
Viggo Kann
2000-03-20