Metric-Preserving Reduction of Earth Mover's Distance (Mathematical Programming in the 21st Century : Optimization Modeling and Algorithms)
Yuichi Takano, Yoshitsugu Yamamoto · Kyoto University Research Information Repository (Kyoto University) · 2009
We prove that the earth mover's distance problem reduces to a problem with half the number of constraints regardless of the ground distance, and propose a further reduced formulation when the ground distance comes from a graph with a homogeneous neighborhood structure.