Approximate classification via earthmover metrics
Approximate classification via earthmover metrics
复制标题
通过推土机指标进行近似分类
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
É. Tardos
中科院分区：
文献类型：
--
作者：
Aaron Archer;Jittat Fakcharoenphol;Chris Harrelson;Robert Krauthgamer;Kunal Talwar;É. Tardos
给定一个度量空间 (X, d)，X 上概率分布的自然距离测度就是推土机度量。我们使用推土机度量的随机舍入来为两个众所周知的分类问题（即度量标记和 0 扩展）设计新的近似算法。我们的第一个结果是针对 0 扩展问题。我们证明，如果终端度量可以用参数 α 分解（例如，平面度量可以用 α = O(1) 分解），那么基于推土机的线性程序（对于 0-扩展）可以舍入到 O(α) 因子内。我们的第二个结果是度量标记的 O(log n) 近似，使用概率树嵌入的方式与 O(log k)-Kleinberg 和 Tardos 的近似。 （这里，n 是节点数，k 是标签数。）当输入图是树时，关键元素是对基于推土机的线性程序（用于度量标签）进行舍入，而不增加解决方案的成本。这种舍入方法还为 Chekuri 等人所述的结果提供了替代证明，即当输入图是树时，基于推土机的线性程序是积分的。我们简单且有建设性的舍入技术有助于理解推土机指标，并且可能具有独立的兴趣。
Given a metric space (X, d), a natural distance measure on probability distributions over X is the earthmover metric. We use randomized rounding of earthmover metrics to devise new approximation algorithms for two well-known classification problems, namely, metric labeling and 0-extension.Our first result is for the 0-extension problem. We show that if the terminal metric is decomposable with parameter α (e.g., planar metrics are decomposable with α = O(1)), then the earthmover based linear program (for 0-extension) can be rounded to within an O(α) factor.Our second result is an O(log n)-approximation for metric labeling, using probabilistic tree embeddings in a way very different from the O(log k)-approximation of Kleinberg and Tardos. (Here, n is the number of nodes, and k is the number of labels.) The key element is rounding the earthmover based linear program (for metric labeling) without increasing the solution's cost, when the input graph is a tree. This rounding method also provides an alternate proof to a result stated in Chekuri et al., that the earthmover based linear program is integral when the input graph is a tree.Our simple and constructive rounding techniques contribute to the understanding of earthmover metrics and may be of independent interest.