A generic auction algorithm for the minimum cost network flow problem

DOI10.1007/BF01299450zbMath0792.90024OpenAlexW2057750651MaRDI QIDQ1315446

Dimitri P. Bertsekas, David A. Castanon

Publication date: 10 March 1994

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

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

zbMATH Keywords

transportationshortest path problem\(\varepsilon\)-relaxation methodassignment auction algorithmlinear minimum cost network flow

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items (6)

The invisible hand algorithm: solving the assignment problem with statistical physics ⋮ Uncertain minimum cost flow problem ⋮ The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation ⋮ A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs ⋮ Time-dependent optimization of a multi-item uncertain supply chain network: a hybrid approximation algorithm ⋮ Auction algorithms for network flow problems: A tutorial introduction

Uses Software

• NETGEN
• RELAX4

Cites Work

• The auction algorithm for the transportation problem
• Dual coordinate step methods for linear network flow problems
• Parallel synchronous and asynchronous implementations of the auction algorithm
• Auction algorithms for network flow problems: A tutorial introduction
• The auction algorithm: A distributed relaxation method for the assignment problem
• Finding Minimum-Cost Circulations by Successive Approximation
• An Auction Algorithm for Shortest Paths
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Reverse Auction and the Solution of Inequality Constrained Assignment Problems
• An Appraisal of Some Shortest-Path Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A generic auction algorithm for the minimum cost network flow problem