On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
From MaRDI portal
Publication:4229424
DOI10.1137/S0097539795296334zbMath1012.65015MaRDI QIDQ4229424
Vineet Bafna, Richa Agarwala, Martin Farach, Mikkel Thorup, Mike S. Paterson
Publication date: 22 February 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Numerical smoothing, curve fitting (65D10) Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25)
Related Items
Combining polynomial running time and fast convergence for the disk-covering method. ⋮ Testing metric properties ⋮ Cumulative disease progression models for cross-sectional data: A review and comparison ⋮ On the edge \(l_{\infty }\) radius of Saitou and Nei's method for phylogenetic reconstruction ⋮ A GA-PCA approach for power sector performance ranking based on machine productivity ⋮ An integrated framework for continuous assessment and improvement of manufacturing systems ⋮ L-Infinity Optimization to Linear Spaces and Phylogenetic Trees ⋮ Learning a tree-structured Ising model in order to make predictions ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ UPGMA and the normalized equidistant minimum evolution problem ⋮ Finding the closest ultrametric ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ On the hardness of inferring phylogenies from triplet-dissimilarities ⋮ An integrated PCA DEA framework for assessment and ranking of manufacturing systems based on equipment performance ⋮ FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees ⋮ Fast neighbor joining ⋮ A lower bound on the edge \(l_{\infty }\) radius of Saitou and Nei's method for phylogenetic reconstruction ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces ⋮ Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
