On constant factor approximation for earth mover distance over doubling metrics

Shi Li

Given a metric space $(X,d_X)$, the earth mover distance between two distributions over $X$ is defined as the minimum cost of a bipartite matching between the two distributions. Th…