Sorting by Bounded Permutations

Abstract

Let P be a predicate applicable to permutations. A permutation that satisfies P is called a generator. Given a permutation $pi$, MinSort_P is the problem of finding a shortest sequence of generators that, when composed with $pi$, yields the identity permutation. The length of this sequence is called the P distance of $pi$. Diam_P is the problem of finding the longest such distance for permutations of a given length. MinSort_P and Diam_P, for some choices of P, have applications in the study of genome rearrangements and in the design of interconnection networks.

This dissertation considers generators that are swaps, reversals, or block-moves. Distance bounds on these generators are introduced and the corresponding problems are investigated. Reduction results, graph-theoretic models, exact and approximation algorithms, and heuristics for these problems are presented. Experimental results on the heuristics are also provided.

When the bound is a function of the length of the permutation, there are several sorting problems such as sorting by block-moves and sorting by reversals whose bounded variants are at least as difficult as the corresponding unbounded problems. For some bounded problems, a strong relationship exists between finding optimal sorting sequences and correcting the relative order of individual pairs of elements. This fact is used in investigating MinSort_P and Diam_P for two particular predicates.

A short block-move is a generator that moves an element at most two positions away from its original position. Sorting by short block-moves is solvable in polynomial time for two large classes of permutations: woven bitonic permutations and woven double-strip permutations. For general permutations, a polynomial-time (4/3)-approximation algorithm that computes short block-move distance is devised. The short block-move diameter for length-n permutations is determined.

A short swap is a generator that swaps two elements that have at most one element between them. A polynomial-time 2-approximation algorithm for computing short swap distance is devised and a class of permutations where the algorithm computes the exact short swap distance is determined. Bounds for the short swap diameter for length-n permutations are determined.