Algorithms for the single-source uncapacitated minimum concave-cost network flow problem

DOI10.1007/BF00119934zbMath0753.90027OpenAlexW2048437057MaRDI QIDQ1200636

Panos M. Pardalos, G. M. Guisewite

Publication date: 16 January 1993

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00119934

zbMATH Keywords

global optimizationlocal searchNP-hardminimum concave-cost network flowsingle-source uncapacitated network flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Abstract computational complexity for mathematical programming problems (90C60) Production models (90B30) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Scalable algorithms for designing \(\mathrm{CO}_2\) capture and storage infrastructure, Approximation algorithms for general one-warehouse multi-retailer systems, An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks, An improved branch and bound algorithm for minimum concave cost network flow problems, Strongly polynomial algorithm for a production-transportation problem with concave production cost, Single-path routing of stochastic flows in networks, A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems, Subdeterminants and Concave Integer Quadratic Programming, The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs, Network flow problems and permutationally concave games, Strongly polynomial algorithm for two special minimum concave cost network flow problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constrained global optimization: algorithms and applications
• Checking local optimality in constrained quadratic programming is NP- hard
• Minimum concave-cost network flow problems: Applications, complexity, and algorithms
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Adjacent extreme flows and application to min concave cost flow problems
• A Heuristic Adjacent Extreme Point Algorithm for the Fixed Charge Problem
• A Deterministic Multi-Period Production Scheduling Model with Backlogging
• Minimum Concave Cost Flows in Certain Networks
• A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
• An approximative algorithm for the fixed charge problem
• The fixed charge problem
• Minimum cost routing for static network models