<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-330

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson and Mikkel Thorup, On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (July 1, 1997).

Abstract

We consider the problem of fitting an n x n distance matrix D by a tree metric T. Let e be the distance to the closest tree metric under the Linf norm, that is e=minT{||T-D||inf}. First we present an O(n sup 2) algorithm for finding a tree metric T such that ||T-D||inf <= 3e. Second we show that it is NP-hard to find a tree metric T such that ||T-D||inf <= 9e/8. This paper presents the first algorithm for this problem with a performance guarantee.

<%@ include file="cited.html" %>

R. Ararwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson and M. Thorup, M. "On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)", Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM/SIAM, New York, NY, pp. 365-372 (1996)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>