@techreport{TR-IC-12-27,
   number = {IC-12-27},
   author  = {Priscila Biller and João Paulo Pereira Zanetti and Pedro
                   Feijão and João Meidanis},
   title = {{On the algebraic genome median}},
   month = {December},
   year = {2012},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 15 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       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, Feijão 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. \par In this paper, we study the genome
       median  problem  under the algebraic model, whose complexity is
       currently  open,  proposing  a  more  generalized  form  of the
       problem, the matrix median problem, that can be approximated in
       linear  time  to  a factor of $\frac{4}{3}$ of the optimum. The
       study  of  the  matrix median might help in the solution of the
       algebraic median problem.
  }
}