Approximate classification via earthmover metrics

Abstract

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-exteneion 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.