Efficient Computations of ℓ1 and ℓ ∞  Rearrangement Distances

Recently, a new pattern matching paradigm was proposed,

pattern matching with address errors

. In this paradigm approximate string matching problems are studied, where the content is unaltered and only the locations of the different entries may change. Specifically, a broad class of problems in this new paradigm was defined – the class of

rearrangement errors

. In this type of errors the pattern is transformed through a sequence of

rearrangement operations

, each with an associated

cost

. The natural ℓ

1

and ℓ

2

rearrangement systems were considered. A variant of the ℓ

1

-rearrangement distance problem seems more difficult – where the pattern is a general string that may have repeating symbols. The best algorithm presented for the general case is

O

(

nm

). In this paper, we show that even for general strings the problem can be approximated in linear time! This paper also considers another natural rearrangement system – the ℓ

 ∞ 

rearrangement distance

. For this new rearrangement system we provide efficient exact solutions for different variants of the problem, as well as a faster approximation.