We consider the problem of fitting an n by n distance matrix D by a tree metric T. This problem is NP-hard for most reasonable distance functions between D and T. Recently, an approximation algorithm was discovered which achieves a factor of 3 approximation to the L-infinity best fitting tree. We call this method the Single Pivot (SP) heuristic. We will describe an extension of the SP heuristic, the Double Pivot (DP) heuristic, and show that DP achieve good results compared with the Neighbor Joining heuristic both on biological and random data.
(Joint work with Prof. Martin Farach.)