Design a greedy algorithm for the Multiple Breakpoints Dista

Design a greedy algorithm for the Multiple Breakpoints Distance problem and evaluate its approximation ratio.

Solution

Breakpoint Distance problem: given a set of permutations ¹,...,^k, nd an ancestral permutation such that sum(br(ⁱ, ), for i in xrange(1,k)) is minimal, where br(ⁱ, ) is the number of breakpoints between ⁱ and .

we defined the number of breakpoints in a permutations as the number of non-adjacent consecutive numbers. This notion can be generalized to define breakpoints between two permutations, br(¹, ²) as follows: for each number x₁, x₂, x₃, ... x_n in ¹ substitute i for x_i. Similarly, for each number y₁, y₂, y₃, ... y_n in ² substitute i for y_k where y_k = x_i, and count the number of breakpoints in ². In other words, impose the ordering of ¹ on ² and count the number of breakpoints in ².

For example:

¹ = [0,1,4,3,2,5,6,7]

² = [0,1,2,3,4,6,5,7]

Imposing ¹\'s order on ²gives:

^2\' = [0,1,4,3,2,6,5,7]   (4 -> 2, 2 -> 4)

this gives 3 breakpoints [0,1|4,3,2|6,5|7].