Polynomial auction algorithms for shortest paths

DOI10.1007/BF01302891zbMath0835.90111OpenAlexW2119991623MaRDI QIDQ1804574

Maria Grazia Scutellà, Stefano Pallottino, Dimitri P. Bertsekas

Publication date: 11 June 1995

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01302891

zbMATH Keywords

shortest pathnetwork optimizationauction algorithmstrongly polynomial variations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items

An auction algorithm for the max-flow problem ⋮ Parallel asynchronous label-correcting methods for shortest paths ⋮ On Some Special Network Flow Problems: The Shortest Path Tour Problems ⋮ The stochastic shortest path problem: a polyhedral combinatorics perspective ⋮ 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 ⋮ Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks

Uses Software

• NETGEN

Cites Work

• Unnamed Item
• Unnamed Item
• An \(O(EV\log^2V)\) algorithm for the maximal flow problem
• Shortest path methods: A unifying approach
• A new algorithm for the assignment problem
• An Auction Algorithm for Shortest Paths
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems