Dual coordinate step methods for linear network flow problems

DOI10.1007/BF01589405zbMath0664.90031MaRDI QIDQ1115790

Jonathan Eckstein, Dimitri P. Bertsekas

Publication date: 1988

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

assignment problemcomputational experiencedistributed algorithmsauction algorithmasynchronous algorithmsminimum-cost flow\(\epsilon \) -complementary slackness\(\epsilon \) -relaxation algorithmlinear-cost network flowserial complexities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items

Data parallel computing for network-structured optimization problems, Spoke contour conversion for coverage diagrams, The invisible hand algorithm: solving the assignment problem with statistical physics, The assignment problem revisited, Far-field reflector problem and intersection of paraboloids, A decision support system for the single-depot vehicle rescheduling problem, Minimum-cost flow algorithms: an experimental evaluation, Parallel Auction Algorithm for Bus Rescheduling, A survey of dynamic network flows, The auction algorithm for the transportation problem, Algorithms and codes for dense assignment problems: The state of the art, 3/4-Discrete Optimal Transport, Optimal transport: discretization and algorithms, Critical objective function values in linear sum assignment problems, On the computational behavior of a polynomial-time network flow algorithm, New scaling algorithms for the assignment and minimum mean cycle problems, On the convergence of the affine-scaling algorithm, Auction algorithms for network flow problems: A tutorial introduction, A simple effective heuristic for embedded mixed-integer quadratic programming, A forward/reverse auction algorithm for asymmetric assignment problems, A comparison of two algorithms for the assignment problem, Implementation and test of auction methods for solving generalized network flow problems with separable convex cost, Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems, Some aspects of parallel and distributed iterative algorithms - a survey, A generic auction algorithm for the minimum cost network flow problem, The maximum flow problem: A max-preflow approach, Discrete optimal transport: complexity, geometry and applications

Uses Software

• NETGEN
• RELAX4

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• An iterative row-action method for interval convex programming
• Termination detection for diffusing computations
• The auction algorithm: A distributed relaxation method for the assignment problem
• A forward/reverse auction algorithm for asymmetric assignment problems
• Chaotic relaxation
• Distributed Asynchronous Relaxation Methods for Convex Network Flow Problems
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A unified framework for primal-dual methods in minimum cost network flow problems
• Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs
• Nonlinear Network Programming on Vector Supercomputers: A Study on the CRAY X-MP
• Complexity of network synchronization
• Relaxation Methods for Network Flow Problems with Convex Arc Costs
• Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
• On the convergence of a block successive over-relaxation method for a class of linear complementarity problems
• 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
• A Class of Decentralized Routing Algorithms Using Relaxation
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• Convex Analysis
• Minimization of unsmooth functionals