y

Abstract For a string A = a1: : : an, a reversal ae(i; j), 1 ^ i ^ j ^ n, transforms the string A into a string A 0 = a1: : : ai\Gamma 1ajaj\Gamma 1: : : aiaj+1: : : an, that is, the reversal ae(i; j) reverses the order of symbols in the substring ai: : : aj of A. In a case of signed strings, where each symbol is given a sign + or \Gamma, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B. Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k * 1. The main result of the paper is an O(k 2)-approximation algorithm running in time O(n). For instances with 3! k ^ O