The median of kxe2x89xa53 genomes was originally defined to find a compromise genome indicative of a common ancestor. However, in gene order comparisons, the usual definitions based on minimizing the sum of distances to the input genomes lead to degenerate medians reflecting only one of the input genomes. Near-medians, consisting of equal samples of gene adjacencies from all the input genomes, were designed to restore the idea of compromise to the median problem.