Dual coordinate step methods for linear network flow problems
type: Item
instance of: scholarly article
title: Dual coordinate step methods for linear network flow problems
zbMATH Open document ID: 0664.90031
DOI: 10.1007/BF01589405
author: Dimitri P. Bertsekas
author: Jonathan Eckstein
published in: Mathematical Programming. Series A. Series B
publication date: 1988-01-01T00:00:00Z
review text: We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion of \(\epsilon\)-complementary slackness, and most do not explicitly manipulate any ``global'' objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of new serial computational complexity results. We develop the basic theory of these methods and present two specific methods, the \(\epsilon\)-relaxation algorithm for the minimum-cost flow problem, and the auction algorithm for the assignment problem. We show how to implement these methods with serial complexities of \(O(N^ 3\log NC)\) and O(NA log NC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement \(\epsilon\)- relaxation in a completely asynchronous, ``chaotic'' environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4087396
zbMATH Keywords: distributed algorithms
zbMATH Keywords: asynchronous algorithms
zbMATH Keywords: linear-cost network flow
zbMATH Keywords: \(\epsilon \) -complementary slackness
zbMATH Keywords: \(\epsilon \) -relaxation algorithm
zbMATH Keywords: minimum-cost flow
zbMATH Keywords: auction algorithm
zbMATH Keywords: assignment problem
zbMATH Keywords: serial complexities
zbMATH Keywords: computational experience
describes a project that uses: NETGEN
describes a project that uses: RELAX4
MaRDI profile type: Publication
cites work: A Fast and Simple Algorithm for the Maximum Flow Problem
cites work: Complexity of network synchronization
cites work: The auction algorithm: A distributed relaxation method for the assignment problem
cites work: A unified framework for primal-dual methods in minimum cost network flow problems
cites work: A forward/reverse auction algorithm for asymmetric assignment problems
cites work: Distributed Asynchronous Relaxation Methods for Convex Network Flow Problems
cites work: Relaxation Methods for Network Flow Problems with Convex Arc Costs
cites work: Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
cites work: Q4001523
cites work: An iterative row-action method for interval convex programming
cites work: Chaotic relaxation
cites work: On the convergence of a block successive over-relaxation method for a class of linear complementarity problems
cites work: Termination detection for diffusing computations
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Q3292914
cites work: Faster scaling algorithms for general graph matching problems
cites work: Faster Scaling Algorithms for Network Problems
cites work: A shortest augmenting path algorithm for dense and sparse linear assignment problems
cites work: NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
cites work: Q3688092
cites work: Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs
cites work: Q4739657
cites work: Minimization of unsmooth functionals
cites work: Q3730336
cites work: Convex Analysis
cites work: A Class of Decentralized Routing Algorithms Using Relaxation
cites work: A strongly polynomial minimum cost circulation algorithm
cites work: Nonlinear Network Programming on Vector Supercomputers: A Study on the CRAY X-MP
description: scientific article; zbMATH DE number 4087396