Strongly polynomial time algorithms for certain concave minimization problems on networks

DOI10.1016/0167-6377(93)90102-MzbMath0794.90015MaRDI QIDQ1317011

Nguyen Dinh Dan, Hoang Tuy, Saied Ghannadan

Publication date: 17 April 1994

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

parametric methodstrongly polynomial algorithmminimum concave cost flow problemproduction- transportation problemsingle source uncapacitated network

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Sensitivity, stability, parametric optimization (90C31) Production models (90B30) Deterministic network models in operations research (90B10)

Related Items

Approximation algorithms for general one-warehouse multi-retailer systems, 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, A general purpose exact solution method for mixed integer concave minimization problems, A simplicial branch-and-bound algorithm conscious of special structures in concave minimization problems, The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs, Bounds for global optimization of capacity expansion and flow assignment problems, Strongly polynomial algorithm for two special minimum concave cost network flow problems

Cites Work

• Quadratic programming with one negative eigenvalue is NP-hard
• Parametric simplex algorithms for solving a special class of nonconvex minimization problems
• Linear multiplicative programming
• Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
• Minimizing the sum of a convex function and a specially structured nonconvex function
• Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources
• An efficient solution method for rank two quasiconcave minimization problems
• A polynomial time solvable concave network flow problem
• On Nonlinear Fractional Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item