A polynomial time solvable concave network flow problem

DOI10.1002/NET.3230230208MaRDI QIDQ5287447zbMATH OpenOpenAlexFDO

Authors Geoffrey 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

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

Recommendations

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

Cited in

(21)

• Strongly polynomial time algorithms for certain concave minimization problems on networks
• Minimizing a linear multiplicative-type function under network flow constraints
• An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks
• Strong polynomial-time solvability of a minimum concave cost network flow problem.
• A strongly polynomial contraction-expansion algorithm for network flow problems
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• 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
• A concavity result for network design problems
• 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
• On linear multiplicative programming.
• On the computational complexity of minimum-concave-cost flow in a two-dimensional grid
• Strongly polynomial algorithm for two special minimum concave cost network flow problems
• scientific article; zbMATH DE number 6402605 (Why is no real title available?)
• A general purpose exact solution method for mixed integer concave minimization problems
• Open questions in complexity theory for numerical optimization
• A conic quadratic formulation for a class of convex congestion functions in network flow problems
• Global and local search algorithms for concave cost transshipment problems
• The binary network flow problem is logspace complete for P

This page was built for publication: A polynomial time solvable concave network flow problem

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