Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM SORTING BY REVERSALS

• INSTANCE: Permutation $\pi$ of the numbers 1 to n.

• SOLUTION: A sequence $\rho_1, \rho_2,\ldots,\rho_t$ of reversals of intervals such that $\pi\cdot\rho_1\cdot\rho_2\cdots\rho_t$ is the identity permutation. A reversal of an interval [i,j] is the permutation $(1,2,\ldots,i-1,j,j-1,\ldots,i+1,i,j+1,\ldots,n)$.

• 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 $\rho(i,j,k)$ where i<j<k is the permutation $(1,2,\ldots,i-1,j,\ldots,k-1,i\ldots,j-1,k,\ldots,n)$ [52].