An out-of-kilter method for the algebraic circulation problem

DOI10.1016/0166-218X(85)90055-1MaRDI QIDQ1057166zbMATH OpenOpenAlexFDO

Authors Peter Brucker, W. Papenjohann

Publication date 1985

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(85)90055-1

zbMATH Keywords

algebraic objectivesbottleneck objectivescirculation problemslexicographic multicriteria objectivesminimum cost network flowordinal sumsout-of-kilter methodscaling techniquessum objectives

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Linear programming (90C05) Programming in abstract spaces (90C48)

Review text

An out-of-kilter method for circulation problems with algebraic objectives which cover sum objectives, bottleneck objectives, ordinal sums, lexicographic multicriteria objectives, and others is developed. If the method is applied to path problems, assignment problems, transportation problems and minimum cost network flow problems one gets algorithms with a complexity not worse than the complexity of so far best known algorithms. Also scaling techniques are applied showing that the algebraic circulation problem is polynomially solvable.

Recommendations

• A scaling out-of-kilter algorithm for minimum cost flow
• Finding Minimum-Cost Circulations by Successive Approximation
• Faster Scaling Algorithms for Network Problems
• scientific article; zbMATH DE number 3900474
• A strongly polynomial minimum cost circulation algorithm

Cites work

• A general Hungarian method for the algebraic transportation problem
• Algebraic Linear Programming
• An algebraic approach to assignment problems
• An algorithm for algebraic assignment problems
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• An out-of-kilter method for the algebraic circulation problem
• Duality for algebraic linear programming
• scientific article; zbMATH DE number 3904362 (Why is no real title available?)
• scientific article; zbMATH DE number 3724474 (Why is no real title available?)
• scientific article; zbMATH DE number 3759934 (Why is no real title available?)
• scientific article; zbMATH DE number 3490714 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• Linear and combinatorial optimization in ordered algebraic structures
• Monotone networks
• The Role of Unimodularity in Applying Linear Inequalities to Combinatorial Theorems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Weakly admissible transformations for solving algebraic assignment and transportation problems

Cited in

(3)

• An out-of-kilter method for the algebraic circulation problem
• Circulations, Fuzzy Relations and Semirings
• scientific article; zbMATH DE number 7405332 (Why is no real title available?)

This page was built for publication: An out-of-kilter method for the algebraic circulation problem

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