I∞-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) over cap 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 {x is an element of K: x < u) (we let x < y 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, <), the cone of convex functions defined on a subset of R-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). (C) 2000 Academic Press.