l(infinity)-Approximation via Subdominants

Given a vector u and a certain subset K of a real vector space E, the problem of l(infinity)-approximation involves determining an element;u in K nearest to u in the sense of the l(infinity)-error norm. The subdominant u * of u is the upper bound (if it exists) of the set {xinK : x precedesu} (we let x precedesy if all coordinates of x are smaller than or equal to the corresponding coordinates of y). We present general conditions on K under which a simple relationship between the subdominant of u and a best l(infinity)-approximation holds. We specify this result by taking as K the cone of isotonic functions defined on a poset (X, precedes), the cone of convex functions defined on a subset of ℝ(N), the cone of ultrametrics on a set X, and the cone of tree metrics on a set X with fixed distances to a given vertex. This leads to simple optimal algorithms for the problem of best l(infinity)-fitting of distances by ultrametrics and by tree metrics preserving the distances to a fixed vertex (the latter provides a 3-approximation algorithm for the problem of fitting a distance by a tree metric). This simplifies the recent results of Farach, Kannan, and Warnow (1995) and of Agarwala et al. (1996). Copyright 2000 Academic Press.