An Auction Algorithm for Shortest Paths

DOI10.1137/0801026zbMath0754.90060OpenAlexW2119312244WikidataQ56560032 ScholiaQ56560032MaRDI QIDQ4012426

Dimitri P. Bertsekas

Publication date: 27 September 1992

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0801026

zbMATH Keywords

directed graphshortest pathsauction algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Parallel numerical computation (65Y05) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Shortest path reoptimization vs resolution from scratch: a computational comparison ⋮ The assignment problem revisited ⋮ An auction algorithm for the max-flow problem ⋮ On Some Special Network Flow Problems: The Shortest Path Tour Problems ⋮ Efficient parallel algorithms for the minimum cost flow problem ⋮ The stochastic shortest path problem: a polyhedral combinatorics perspective ⋮ Group preference modeling for intelligent shared environments: social welfare beyond the sum ⋮ Dual bounds of a service level assignment problem with applications to efficient pricing ⋮ Auction algorithms for network flow problems: A tutorial introduction ⋮ Complexity analysis and optimization of the shortest path tour problem ⋮ An auction-based approach for the re-optimization shortest path tree problem ⋮ Polynomial auction algorithms for shortest paths ⋮ An extension of labeling techniques for finding shortest path trees ⋮ A generic auction algorithm for the minimum cost network flow problem