An Auction Algorithm for Shortest Paths

DOI10.1137/0801026MaRDI QIDQ4012426zbMATH OpenOpenAlexWikidataFDO

Authors 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

auction algorithmdirected graphshortest paths

Mathematics Subject Classification ID

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

Recommendations

• Parallel shortest path auction algorithms
• Polynomial auction algorithms for shortest paths
• scientific article; zbMATH DE number 1424207
• Shortest path methods: A unifying approach
• Auction algorithms for shortest hyperpath problems

Cited in

(33)

• An extension of labeling techniques for finding shortest path trees
• A parallel shortest path algorithm
• Auction algorithms for network flow problems: A tutorial introduction
• The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm
• A generic auction algorithm for the minimum cost network flow problem
• Parallel shortest path auction algorithms
• Efficient parallel algorithms for the minimum cost flow problem
• Shortest path auction algorithm without contractions using virtual source concept
• Dual bounds of a service level assignment problem with applications to efficient pricing
• Polynomial auction algorithms for shortest paths
• An auction algorithm for the max-flow problem
• The assignment problem revisited
• The stochastic shortest path problem: a polyhedral combinatorics perspective
• An auction-based approach for the re-optimization shortest path tree problem
• Auction algorithms for shortest hyperpath problems
• scientific article; zbMATH DE number 4016203 (Why is no real title available?)
• ON SOLVING SHORTEST PATHS WITH A LEAST-SQUARES PRIMAL-DUAL ALGORITHM
• Shortest‐path methods: Complexity, interrelations and new propositions
• Shortest path methods: A unifying approach
• Dual algorithms for the shortest path tree problem
• scientific article; zbMATH DE number 1560338 (Why is no real title available?)
• Scaling Algorithms for the Shortest Paths Problem
• scientific article; zbMATH DE number 1424207 (Why is no real title available?)
• Shortest path reoptimization vs resolution from scratch: a computational comparison
• Group preference modeling for intelligent shared environments: social welfare beyond the sum
• On Some Special Network Flow Problems: The Shortest Path Tour Problems
• An Appraisal of Some Shortest-Path Algorithms
• Graph collapsing in shortest path auction algorithms
• A mechanism design approach for multi-party machine learning
• Projection methods for finding the greatest element of the intersection of max-closed convex sets
• Complexity analysis and optimization of the shortest path tour problem
• A new \(O(n^ 2)\) shortest chain algorithm
• The auction algorithm for the transportation problem

This page was built for publication: An Auction Algorithm for Shortest Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4012426)