The Shortlist Method for fast computation of the Earth Mover's Distance and finding optimal solutions to transportation problems.
Ontology highlight
ABSTRACT: 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
SUBMITTER: Gottschlich C
PROVIDER: S-EPMC4195716 | biostudies-literature | 2014
REPOSITORIES: biostudies-literature
ACCESS DATA