Auction algorithms for network flow problems: A tutorial introduction
assignmentsauction algorithmnetworks flow problemsshortest pathssurvey papertransportationtransshipment
Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic network models in operations research (90B10) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35)
The auction algorithm for networks flow problems is motivated by a real auction where persons compete for objects by iteratively raising the prices of these objects through competitive bidding. In the auction algorithm the bidding is controlled by an minimum \(\varepsilon\)-increase in every step and the procedure finishes if a feasible solution is at hand. After describing the basic auction algorithm and some variants of it, the survey paper of Bertsekas shows how the method can be applied to the problems of linear network flows, shortest paths, assignments, maximum flows, transportation flows and transshipment flows. The paper contains a large number of examples and figures which make it easy for the reader to understand the ideas of the auction approach.
- The auction algorithm for assignment and other network flow problems
- A generic auction algorithm for the minimum cost network flow problem
- An auction algorithm for the max-flow problem
- The auction algorithm for the transportation problem
- Implementation and test of auction methods for solving generalized network flow problems with separable convex cost
- A computational analysis of the auction algorithm
- A Descent Numerical Method for Optimization Problems with Nondifferentiable Cost Functionals
- A Fast and Simple Algorithm for the Maximum Flow Problem
- A forward/reverse auction algorithm for asymmetric assignment problems
- A generic auction algorithm for the minimum cost network flow problem
- A new algorithm for the assignment problem
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
- Adaptive aggregation methods for infinite horizon dynamic programming
- An algorithm for ranking paths that may contain cycles
- An Appraisal of Some Shortest-Path Algorithms
- An Auction Algorithm for Shortest Paths
- Analysis of Preflow Push Algorithms for Maximum Network Flow
- Dual coordinate step methods for linear network flow problems
- Finding Minimum-Cost Circulations by Successive Approximation
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3912096 (Why is no real title available?)
- scientific article; zbMATH DE number 3961334 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- Parallel shortest path auction algorithms
- Parallel synchronous and asynchronous implementations of the auction algorithm
- Polynomial auction algorithms for shortest paths
- Reverse Auction and the Solution of Inequality Constrained Assignment Problems
- The auction algorithm: A distributed relaxation method for the assignment problem
- A generic auction algorithm for the minimum cost network flow problem
- Data parallel computing for network-structured optimization problems
- Auction dynamics: a volume constrained MBO scheme
- Uncertain programming model for uncertain optimal assignment problem
- An auction algorithm for the max-flow problem
- Stochastic downscaling method: application to wind refinement
- The assignment problem revisited
- Center-outward quantiles and the measurement of multivariate risk
- Strategyproof auction mechanisms for network procurement
- Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
- Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
- Empirical optimal transport on countable metric spaces: distributional limits and statistical applications
- Descending price multi-item auctions
- Application of optimal transportation theory to the reconstruction of the early Universe
- Combinatorial auctions for electronic business
- Optimum matchings in weighted bipartite graphs
- Auction algorithms for shortest hyperpath problems
- Optimal transport by omni-potential flow and cosmological reconstruction
- Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem
- Distributed coordination of emergency medical service for angioplasty patients
- The auction algorithm for assignment and other network flow problems
- Numerical solution of the optimal transportation problem using the Monge-Ampère equation
- Parallel Auction Algorithm for Bus Rescheduling
- scientific article; zbMATH DE number 679856 (Why is no real title available?)
- Properties of the DGS-auction algorithm
- Distributed optimization of P2P live streaming overlays
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
- Group preference modeling for intelligent shared environments: social welfare beyond the sum
- Optimal transport: fast probabilistic approximation with exact solvers
- Coordinated road-network search route planning by a team of UAVs
- The vehicle rescheduling problem: Model and algorithms
- Auction protocols for decentralized scheduling
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- Multi-agent based optimal equilibrium selection with resilience constraints for traffic flow
- Entropic model predictive optimal transport over dynamical systems
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- A study of auction mechanisms for multilateral procurement based on subgradient and bundle methods
- Automatic coarsening in algebraic multigrid utilizing quality measures for matching-based aggregations
- A review on design inspired subsampling for big data
- Nonparametric measure-transportation-based methods for directional data
- Unbalanced optimal transport, from theory to numerics
- Optimal transport-inspired deep learning framework for slow-decaying Kolmogorov n-width problems: exploiting Sinkhorn loss and Wasserstein kernel
- Used car salesman problem: a differential auction-barter market
- Simultaneous independent online auctions with discrete bid increments
- A pricing approach for bandwidth allocation in differentiated service networks
- The Monge-Ampère-Kantorovich approach to reconstruction in cosmology
This page was built for publication: Auction algorithms for network flow problems: A tutorial introduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1202585)
