The auction algorithm: A distributed relaxation method for the assignment problem

DOI10.1007/BF02186476zbMath0788.90055MaRDI QIDQ1320412

Dimitri P. Bertsekas

Publication date: 20 April 1994

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

zbMATH Keywords

Jacobi-like relaxation methodmassively parallelizable algorithmworst- case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Parallel numerical computation (65Y05) Auctions, bargaining, bidding and selling, and other market models (91B26) Numerical methods for mathematical programming, optimization and variational techniques (65K99)

Related Items (62)

Data parallel computing for network-structured optimization problems ⋮ Interpolating between random walks and optimal transportation routes: flow with multiple sources and targets ⋮ On combined minmax-minsum optimization ⋮ The assignment problem revisited ⋮ Data-level parallel solution of min-cost network flow problems using \(\varepsilon\)-relaxations ⋮ Distributed coordination of emergency medical service for angioplasty patients ⋮ A multiscale semi-smooth Newton method for optimal transport ⋮ Massively parallel augmenting path algorithms for the assignment problem ⋮ The singly constrained assignment problem: An AP basis algorithm ⋮ Sparsity and independence: balancing two objectives in optimization for source separation with application to fMRI analysis ⋮ Dual coordinate step methods for linear network flow problems ⋮ An efficient cost scaling algorithm for the assignment problem ⋮ Routing and capacity assignment in backbone communication networks ⋮ Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem ⋮ Efficient parallel algorithms for the minimum cost flow problem ⋮ Comparing problem formulations for coupled sets of components ⋮ Geometry Helps to Compare Persistence Diagrams ⋮ Gross substitutability: an algorithmic survey ⋮ Walrasian equilibria from an optimization perspective: A guide to the literature ⋮ A distributed simplex algorithm for degenerate linear programs and multi-agent assignments ⋮ Multivariate Rank-Based Distribution-Free Nonparametric Testing Using Measure Transportation ⋮ Dynamic task allocation based on auction in robotic mobile fulfilment system ⋮ Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching ⋮ On the Stability of Multigraded Betti Numbers and Hilbert Functions ⋮ Properties of the DGS-auction algorithm ⋮ Vector copulas ⋮ Optimal assignment of resources to strengthen the weakest link in an uncertain environment ⋮ The auction algorithm for the transportation problem ⋮ Distributed optimization of P2P live streaming overlays ⋮ Solution of large dense transportation problems using a parallel primal algorithm ⋮ Sets in excess demand in simple ascending auctions with unit-demand bidders ⋮ Parallel Aggregation Based on Compatible Weighted Matching for AMG ⋮ New optimal algorithm of data association for multi-passive-sensor location system ⋮ Critical objective function values in linear sum assignment problems ⋮ New scaling algorithms for the assignment and minimum mean cycle problems ⋮ A heuristic for the time constrained asymmetric linear sum assignment problem ⋮ Topological design of computer communication networks -- the overall design problem ⋮ The importance of memory for price discovery in decentralized markets ⋮ Dual bounds of a service level assignment problem with applications to efficient pricing ⋮ Collaborative assignment using belief-desire-intention agent modeling and negotiation with speedup strategies ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ Auction algorithms for network flow problems: A tutorial introduction ⋮ Bargaining dynamics in exchange networks ⋮ Assignment problems with changeover cost ⋮ Metrics and barycenters for point pattern data ⋮ A faster data assignment algorithm for maximum likelihood-based multitarget motion tracking with bearings-only measurements ⋮ Multiplier methods: A survey ⋮ A new efficient algorithm for optimal assignment of smart weapons to targets ⋮ Economic efficiency requires interaction ⋮ Wasserstein Dictionary Learning: Optimal Transport-Based Unsupervised Nonlinear Dictionary Learning ⋮ An Algorithm for Optimal Transport between a Simplex Soup and a Point Cloud ⋮ A forward/reverse auction algorithm for asymmetric assignment problems ⋮ A comparison of two algorithms for the assignment problem ⋮ The two-machine total completion time flow shop problem ⋮ A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem ⋮ Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems ⋮ Efficient Advert Assignment ⋮ Game of Thrones: Fully Distributed Learning for Multiplayer Bandits ⋮ An algorithm for fractional assignment problems ⋮ Some aspects of parallel and distributed iterative algorithms - a survey ⋮ A generic auction algorithm for the minimum cost network flow problem ⋮ Sliced and Radon Wasserstein barycenters of measures

Uses Software

• NETGEN
• RELAX4

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Chaotic relaxation
• The assignment game. I: The core
• Distributed Asynchronous Relaxation Methods for Convex Network Flow Problems
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• Distributed asynchronous computation of fixed points
• A unified framework for primal-dual methods in minimum cost network flow problems
• Efficient dual simplex algorithms for the assignment problem
• Signature Methods for the Assignment Problem
• A competitive (dual) simplex method for the assignment problem
• Relaxation Methods for Network Flow Problems with Convex Arc Costs
• Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
• Solving the Assignment Problem by Relaxation
• A new algorithm for the assignment problem
• The Economics of Matching: Stability and Incentives
• 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
• Asynchronous Iterative Methods for Multiprocessors
• 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

This page was built for publication: The auction algorithm: A distributed relaxation method for the assignment problem