A polynomial time solvable concave network flow problem

DOI10.1002/net.3230230208zbMath0780.90037OpenAlexW1968111265MaRDI QIDQ5287447

G. M. Guisewite, Panos M. Pardalos

Publication date: 5 September 1993

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230230208

zbMATH Keywords

polynomial solvabilitysingle-source uncapacitated concave cost network flow

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items

Minimizing a linear multiplicative-type function under network flow constraints, A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables, An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks, A general purpose exact solution method for mixed integer concave minimization problems, On linear multiplicative programming., Open questions in complexity theory for numerical optimization, Valid inequalities for separable concave constraints with indicator variables, The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs, Probabilistic local search algorithms for concave cost transportation network problems, On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid, Minimum concave cost flow over a grid network, Strongly polynomial algorithm for two special minimum concave cost network flow problems, Strongly polynomial time algorithms for certain concave minimization problems on networks, Global and local search algorithms for concave cost transshipment problems