About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 2004
Conference paper
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.