A unified framework for primal-dual methods in minimum cost network flow problems

DOI10.1007/BF01586087zbMATH Open0567.90023MaRDI QIDQ3683845FDOQ3683845

Authors: Dimitri P. Bertsekas 

Publication date: 1985

Published in: Mathematical Programming (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 5173820
• scientific article; zbMATH DE number 4174642
• On dual minimum cost flow algorithms (extended abstract)
• On dual minimum cost flow algorithms
• A new strongly polynomial dual network simplex algorithm

zbMATH Keywords

relaxationminimum cost flowcapacitated networkout-of-kilter

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Extremal problems in graph theory (05C35)

Cites Work

• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The alternating basis algorithm for assignment problems
• A new algorithm for the assignment problem
• Title not available (Why is that?)
• Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem
• A Class of Decentralized Routing Algorithms Using Relaxation

Cited In (23)

• Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility
• Infinite networks: Minimal cost flows
• A faster data assignment algorithm for maximum likelihood-based multitarget motion tracking with bearings-only measurements
• An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems
• Title not available (Why is that?)
• Dual coordinate step methods for linear network flow problems
• The value of runway time slots for airlines
• A new algorithm for finding the minimum cost flow using the duality principle
• Dual Algorithms for Pure Network Problems
• A dual algorithm for submodular flow problems
• On the computational behavior of a polynomial-time network flow algorithm
• Parallel primal-dual methods for the minimum cost flow problem
• The auction algorithm for the transportation problem
• Restricted Simplicial Decomposition for Symmetric Convex Cost Flow Problems
• Accelerated Dual Descent for Network Flow Optimization
• A survey of dynamic network flows
• Diagnosing Infeasibility in Min-cost Network Flow Problems Part II: Primal Infeasibility
• Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
• A least-squares minimum-cost network flow algorithm
• Models for multimode multicommodity location problems with interdepot balancing requirements
• Title not available (Why is that?)
• The auction algorithm: A distributed relaxation method for the assignment problem
• Multicommodity network flows: A survey. II: Solution methods

Uses Software

• NETGEN

This page was built for publication: A unified framework for primal-dual methods in minimum cost network flow problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3683845)