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.
Code (0)
등록된 구현이 없습니다.
Tasks
Content-Based Image RetrievalImage RetrievalObject TrackingRetrievalSimilar Papers 제목 키워드 기반
Low-Complexity Data-Parallel Earth Mover's Distance Approximations
The Earth Mover's Distance (EMD) is a state-of-the art metric for comparing discrete probability distributions, but its high distinguishability comes at a high cost in computational complexity. Even though linear-complex…
CPUGPURGB2Point: 3D Point Cloud Generation from Single RGB Images
We introduce RGB2Point, an unposed single-view RGB image to a 3D point cloud generation based on Transformer. RGB2Point takes an input image of an object and generates a dense 3D point cloud. Contrary to prior works base…
DenoisingPoint Cloud GenerationEfficient Tracking of Sparse Signals via an Earth Mover's Distance Dynamics Regularizer
Tracking algorithms such as the Kalman filter aim to improve inference performance by leveraging the temporal dynamics in streaming observations. However, the tracking regularizers are often based on the $\ell_p$-norm wh…
Earthmover-based manifold learning for analyzing molecular conformation spaces
In this paper, we propose a novel approach for manifold learning that combines the Earthmover's distance (EMD) with the diffusion maps method for dimensionality reduction. We demonstrate the potential benefits of this ap…
Dimensionality ReductionShortlist Selection With Residual-Aware Distance Estimator for K-Nearest Neighbor Search
In this paper, we introduce a novel shortlist computation algorithm for approximate, high-dimensional nearest neighbor search. Our method relies on a novel distance estimator: the residual-aware distance estimator, that …
Quantization