  The Genome Median Problem is an important problem in phylogenetic
reconstruction under rearrangement models. It can be stated as follows: given
three genomes, find a fourth that minimizes the sum of the pairwise
rearrangement distances between it and the three input genomes. Recently,
Feijao and Meidanis extended the algebraic theory for genome rearrangement to
allow for linear chromosomes, thus yielding a new rearrangement model (the
algebraic model), very close to the celebrated DCJ model. In this paper, we
study the genome median problem under the algebraic model, whose complexity is
currently open, proposing a more general form of the problem, the matrix median
problem. It is known that, for any metric distance, at least one of the corners
is a 4/3-approximation of the median. Our results allow us to compute up to
three additional matrix median candidates, all of them with approximation
ratios at least as good as the best corner, when the input matrices come from
genomes. From the application point of view, it is usually more interesting to
locate medians farther from the corners. We also show a fourth median candidate
that gives better results in cases we tried. However, we do not have proven
bounds for this fourth candidate yet.
