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

DOI10.1080/02331939508844033zbMATH Open0817.65049OpenAlexW2070965920MaRDI QIDQ4764587FDOQ4764587

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

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

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)

Cites Work

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

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.
• On minimum concave cost network flow problems
• A strongly polynomial contraction-expansion algorithm for 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
• Title not available (Why is that?)
• 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)