The optimality conjecture for distance-based tree reconstruction

Let an algorithm reconstruct a general tree from pairwise distance data, and define its $l_\infty$-radius as the largest error tolerance under which it returns the correct tree topology. The RNJ algorithm is Algorithm 3, and let $d$ be an additive metric on a general tree with edge set $E$. Set

$$\Delta=\min_{e\in E}d(e).$$

Optimality conjecture. No distance-based algorithm has $l_\infty$-radius greater than $\frac{1}{4}$ for general trees. Consequently, if this assertion holds, the RNJ algorithm achieves the optimal $l_\infty$-radius $\frac{1}{4}$ for general trees when $\Delta=\min_{e\in E}d(e)$.

The preceding result establishes an $l_\infty$-radius of $\frac{1}{4}$ for RNJ under this choice of $\Delta$; the conjecture asserts that no distance-based method can improve this guarantee.