The auction algorithm for the transportation problem

DOI10.1007/BF02216923zbMath0705.90061OpenAlexW1964486323MaRDI QIDQ918416

Dimitri P. Bertsekas, David A. Castanon

Publication date: 1989

Published in: Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

assignmentauction algorithmcompetitive biddingparallel relaxation method

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Applications of optimal transportation in the natural sciences. Abstracts from the workshop held February 21--27, 2021 (online meeting), Scaling algorithms for unbalanced optimal transport problems, The nested Sinkhorn divergence to learn the nested distance, Geometry Helps to Compare Persistence Diagrams, Wasserstein distances in the analysis of time series and dynamical systems, Limit distributions and sensitivity analysis for empirical entropic optimal transport on countable spaces, Max-Plus Algebraic Statistical Leverage Scores, A graph space optimal transport distance as a generalization of L ^p distances: application to a seismic imaging inverse problem, Auction dynamics: a volume constrained MBO scheme, A fast approach to optimal transport: the back-and-forth method, Distributed optimization of P2P live streaming overlays, Approximation of optimal transport problems with marginal moments constraints, New scaling algorithms for the assignment and minimum mean cycle problems, Dual bounds of a service level assignment problem with applications to efficient pricing, A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem, A review of the use of optimal transport distances for high resolution seismic imaging based on the full waveform, A generic auction algorithm for the minimum cost network flow problem, Empirical Regularized Optimal Transport: Statistical Theory and Applications

Uses Software

• NETGEN
• RELAX4

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• Dual coordinate step methods for linear network flow problems
• The auction algorithm: A distributed relaxation method for the assignment problem
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• A unified framework for primal-dual methods in minimum cost network flow problems
• Efficient dual simplex algorithms for the assignment problem
• A competitive (dual) simplex method for the assignment problem
• Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
• A new algorithm for the assignment problem
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• The alternating basis algorithm for assignment problems
• A Successive Shortest Path Algorithm for The Assignment Problem
• Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem