In this paper we present several natural and realistic ways of modeling the inaccuracies in the distance data. In one model we assume that we have upper and lower bounds for the distances between pairs of species and try to find an additive distance matrix between these bounds. In a second model we are given a partial matrix and asked to find if we can fill in the unspecified entries in order to make the entire matrix additive.
Ultrametric matrices are desirable in biology since the trees then indicate evolutionary time.
We give polynomial time algorithms for some of the problems while showing others to be NP-Complete. For most criteria this optimization problem turns out to be NP-Hard, while we do get polynomial time algorithms for some. This is the first reasonable model for which optimal trees can be found in polynomial time.