Polynomial auction algorithms for shortest paths

DOI10.1007/BF01302891MaRDI QIDQ1804574zbMATH OpenOpenAlexFDO

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

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) Auctions, bargaining, bidding and selling, and other market models (91B26) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An Auction Algorithm for Shortest Paths
• Auction algorithms for shortest hyperpath problems
• Parallel shortest path auction algorithms
• Graph collapsing in shortest path auction algorithms
• Shortest path auction algorithm without contractions using virtual source concept

Cites work

• scientific article; zbMATH DE number 53116 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A new algorithm for the assignment problem
• An Auction Algorithm for Shortest Paths
• An \(O(EV\log^2V)\) algorithm for the maximal flow problem
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Shortest path methods: A unifying approach

Cited in

(14)

• Auction algorithms for shortest hyperpath problems
• Shortest path auction algorithm without contractions using virtual source concept
• Parallel asynchronous label-correcting methods for shortest paths
• Auction algorithms for network flow problems: A tutorial introduction
• The stochastic shortest path problem: a polyhedral combinatorics perspective
• Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks
• An Auction Algorithm for Shortest Paths
• An auction-based approach for the re-optimization shortest path tree problem
• Complexity analysis and optimization of the shortest path tour problem
• On Some Special Network Flow Problems: The Shortest Path Tour Problems
• Graph collapsing in shortest path auction algorithms
• Parallel shortest path auction algorithms
• A mechanism design approach for multi-party machine learning
• An auction algorithm for the max-flow problem

Describes a project that uses

Uses Software

• NETGEN

This page was built for publication: Polynomial auction algorithms for shortest paths

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