The Maximum Nearby Flow Problem

We present a new Linear Programming model that formulates the problem of computing the Kantorovich-Wasserstein distance associated with a truncated ground distance. The key idea of our model is to consider only the quantity of mass that is transported to nearby points and to ignore the quantity of mass that should be transported between faraway pairs of locations. The proposed model has a number of variables that depends on the threshold value used in the definition of the set of nearby points. Using a small threshold value, we can obtain a significant speedup. We use our model to numerically evaluate the percentage gap between the true Wasserstein distance and the truncated Wasserstein distance, using a set of standard grey scale images.