An auction algorithm for the max-flow problem

DOI10.1007/BF02192042zbMath0843.90044MaRDI QIDQ1906750

Dimitri P. Bertsekas

Publication date: 21 February 1996

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

zbMATH Keywords

network optimizationmax-flow problempreflow-push algorithmsauction-like algorithmsequence of augmentations along paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (6)

Descent methods with linesearch in the presence of perturbations ⋮ An auction algorithm for the max-flow problem ⋮ Efficient parallel algorithms for the minimum cost flow problem ⋮ Efficient preflow push algorithms ⋮ Experimental evaluation of solution approaches for the \(K\)-route maximum flow problem ⋮ Computational investigations of maximum flow algorithms

Uses Software

• NETGEN
• RELAX4

Cites Work

• The maximum flow problem: A max-preflow approach
• Auction algorithms for network flow problems: A tutorial introduction
• Polynomial auction algorithms for shortest paths
• An auction algorithm for the max-flow problem
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Maximal Flow Through a Network
• An O(n2log n) parallel max-flow algorithm
• An Auction Algorithm for Shortest Paths
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An auction algorithm for the max-flow problem