Strongly polynomial algorithm for two special minimum concave cost network flow problems

DOI10.1080/02331939508844033MaRDI QIDQ4764587zbMATH OpenOpenAlexFDO

Authors Hoang Tuy, Saied Ghannadan, Athanasios Migdalas, Peter Värbrand

Publication date 6 August 1995

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939508844033

zbMATH Keywords

global optimizationcomplexityconcave minimizationnetwork flow problemproduction-transportation problemstrongly polynomial time algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Recommendations

• Strongly polynomial time algorithms for certain concave minimization problems on networks
• Strong polynomial-time solvability of a minimum concave cost network flow problem.
• The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
• Algorithms for the single-source uncapacitated minimum concave-cost network flow problem

Cites work

• scientific article; zbMATH DE number 2166303 (Why is no real title available?)
• A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
• A polynomial time solvable concave network flow problem
• Adjacent extreme flows and application to min concave cost flow problems
• Algorithms for the single-source uncapacitated minimum concave-cost network flow problem
• An Implicit Enumeration Algorithm for the Concave Cost Network Flow Problem
• An algorithm for the min concave cost flow problem
• An efficient solution method for rank two quasiconcave minimization problems
• Dynamic version of the economic lot size model
• Minimum Concave Cost Flows in Certain Networks
• Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems
• Minimum concave-cost network flow problems: Applications, complexity, and algorithms
• Networks synthesis and optimum network design problems: Models, solution methods and applications
• On a class of capacitated transportation problems
• Open questions in complexity theory for numerical optimization
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Strongly polynomial algorithm for a production-transportation problem with concave production cost
• Strongly polynomial time algorithms for certain concave minimization problems on networks
• The complementary convex structure in global optimization
• The steiner problem in graphs

Cited in

(13)

• Algorithms for the single-source uncapacitated minimum concave-cost network flow problem
• Strong polynomial-time solvability of a minimum concave cost network flow problem.
• A strongly polynomial contraction-expansion algorithm for network flow problems
• On minimum concave cost network flow problems
• Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
• A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
• Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs
• Strongly polynomial time algorithms for certain concave minimization problems on networks
• On the computational complexity of minimum-concave-cost flow in a two-dimensional grid
• scientific article; zbMATH DE number 1560355 (Why is no real title available?)
• A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
• Minimum concave cost flow over a grid network
• A new strongly polynomial dual network simplex algorithm

This page was built for publication: Strongly polynomial algorithm for two special minimum concave cost network flow problems

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