Experiments with the auction algorithm for the shortest path problem
Jesper Larsen, Ib Pedersen · 1999
The auction approach for the shortest path problem as introduced by Bertsekas is tested experimentally. Parallel algorithms using the auction approach are developed and tested. Both the sequential and parallel auction algorithms perform significantly worse than a state-of-the-art Dijkstra-like reference algorithm. 1 Introduction The shortest path problem is one of the classical problems in Operations Research. One usually classifies shortest path algorithms into one of two groups: the labelsetting algorithms (Dijkstra-like) and the label-correcting algorithms (Bellman-Fordlike) . A recent approach to solving shortest path problems is the auction algorithm proposed by Bertsekas in [Ber91]. In [PS91] and [BPS92] the performance of the auction algorithm is enhanced by the use of graph reduction, thereby reducing the worst-case time-complexity from pseudo-polynomial to strongly polynomial. Here we introduce the improved graph reduction scheme, which allows for additional reduction of th...