L-Infinity optimization to Bergman fans of matroids with an application to phylogenetics

Daniel Irving Bernstein

Published 2017-02-16Version 1

Given a dissimilarity map $\delta$ on finite set $X$, we show that the set of ultrametrics (equidistant tree metrics) which are $l^\infty$-nearest to $\delta$ is a tropical polytope. We give an algorithm for computing a superset of its tropical vertices. It was shown by Ardila that the set of all ultrametrics on a finite set of size $n$ is the Bergman fan associated to the matroid underlying the complete graph on $n$ vertices. Therefore, we derive our results in the more general context of Bergman fans of matroids. This more general context allows our algorithm to be applied to dissimilarity maps where only a subset of the entries are known.