PPubMed13 Oct 2014Cited 51×

The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems Shortlist Method for Fast Computation of the Earth Mover's Distance

Carsten Gottschlich, Dominic Schuhmacher, Haipeng Peng

Abstract

As described in the previous section, the simplex-based transportation algorithm consists of two stages: an initialization phase to find a feasible solution and a convergence phase in which the current solution is iteratively improved to optimality. [s3] introduces an additional phase in between these two. The main steps of the Shortlist Method can be outlined as follows: 1. A shortlist is created for each origin containing only a small fraction of all possible destinations. 2. An initial feasible transportation plan is derived from these shortlists (for an example see [pone-0110214-g002], lef

A figure from The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems Shortlist Method for Fast Computation of the Earth Mover's Distance — fig. from the paper

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

The Shortlist Method dramatically speeds up Earth Mover's Distance and transportation problem solving, outperforming existing simplex‑based approaches on large benchmarks.

What’s new

i.Proposes the Shortlist Method to reduce candidate inspections in the revised simplex algorithm
ii.Introduces Modified Russell's Method for faster initial feasible solutions
iii.Provides a benchmark suite and R package implementation for reproducible evaluation
iv.Demonstrates superior runtime performance over state‑of‑the‑art methods across problem sizes up to 3000 origins/destinations

How they did it

Starting from the classic revised simplex algorithm, the authors organize potential pivots into shortlists that are examined sequentially, balancing fewer inspections with needed pivots. They evaluate the approach on synthetic benchmarks generated by randomly placing origins and destinations (100–3000) and measuring total runtimes including initialization and simplex iterations.

What they found

Shortlist Method consistently yields lower total runtimes than all compared initialization‑pivot combinations on benchmarks of 100–3000 origins/destinations
Performance gap widens as problem size grows, as shown in Figures 3 and 4
Implementation runs on a single Intel Core i7 3.20 GHz core in Java, averaging over 100 random instances per size

Caveats

✕Benchmarks are limited to simulated random instances up to 3000 origins/destinations
✕Real‑world datasets were only briefly mentioned; full performance on diverse applications remains untested
✕Method relies on parameter choices (shortlist length, pivot strategy) that may need tuning for specific problems

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems Shortlist Method for Fast Computation of the Earth Mover's Distance

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

Similar papers in all four archives

The paper, in five minutes