Data from: The Shortlist Method for fast computation of the Earth Mover's Distance and finding optimal solutions to transportation problems

Finding solutions to the classical transportation problem is of great
importance, since this optimization problem arises in many engineering and
computer science applications. Especially the Earth Mover's Distance
is used in a plethora of applications ranging from content-based image
retrieval, shape matching, fingerprint recognition, object tracking and
phishing web page detection to computing color differences in linguistics
and biology. Our starting point is the well-known revised simplex
algorithm, which iteratively improves a feasible solution to optimality.
The Shortlist Method that we propose substantially reduces the number of
candidates inspected for improving the solution, while at the same time
balancing the number of pivots required. Tests on simulated benchmarks
demonstrate a considerable reduction in computation time for the new
method as compared to the usual revised simplex algorithm implemented with
state-of-the-art initialization and pivot strategies. As a consequence,
the Shortlist Method facilitates the computation of large scale
transportation problems in viable time. In addition we describe a novel
method for finding an initial feasible solution which we coin Modified
Russell's Method.