l ∞ -approximation via subdominants
l ∞ -approximation via subdominants
复制标题
l ∞ - 通过次主力进行近似
DOI：
10.1006/jmps.1999.1270
复制
发表时间：
2000
影响因子：
1.8
通讯作者：
B. Fichet
中科院分区：
文献类型：
--
作者：
V. Chepoi;B. Fichet
给定一个向量u和实向量空间E的某个子集K，L∞逼近问题涉及确定K中在L∞误差范数意义下离u最近的一个元素u。U的次优u∗是集合{x∈K：x≺u}的上界(如果存在)(如果x的所有坐标都小于或等于y的对应坐标，则设x≺y)。我们给出了K上的一般条件，在该条件下，u的次优与最佳L∞逼近之间的简单关系成立。我们用定义在偏序集(X，≺)上的保序函数的锥，定义在RN的子集上的凸函数的锥，集合X上的超度量的锥，以及集合X上到给定顶点的固定距离的树度量的锥来说明这一结果。这导致了用超度量和通过保持到固定顶点的距离的树度量来最佳L∞拟合问题的简单的优化算法(后者为用树度量来拟合距离的问题提供了一个3-近似算法)。这简化了Farach，Kannan和Warnow(1995)以及Agarwala等人最近的结果。(1996年)。
Abstract Given a vector u and a certain subset K of a real vector space E , the problem of l ∞ -approximation involves determining an element u in K nearest to u in the sense of the l ∞ -error norm. The subdominant u ∗ of u is the upper bound (if it exists) of the set { x ∈ 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 ∞ -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 ∞ -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).