Polynomial auction algorithms for shortest paths

DOI10.1007/BF01302891zbMATH Open0835.90111OpenAlexW2119991623MaRDI QIDQ1804574FDOQ1804574

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

Cites Work

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

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
• On Some Special Network Flow Problems: The Shortest Path Tour Problems
• Complexity analysis and optimization of the shortest path tour problem
• 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

Uses Software

• NETGEN

   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 👍 👎

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)