Send-and-Split Method for Minimum-Concave-Cost Network Flows

DOI10.1287/moor.12.4.634zbMath0667.90036MaRDI QIDQ3820348

Arthur F. jun. Veinott, Clyde l. Monma, Ranel E. Erickson

Publication date: 1987

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.12.4.634

zbMATH Keywords

capacitated networks; dynamic economic-order-quantity problem; minimum-additive-concave-cost nonnegative network flows; send-and-split method

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

90B10: Deterministic network models in operations research

90B05: Inventory, storage, reservoirs

90C39: Dynamic programming

Related Items

Probabilistic analysis of an lp relaxation bound for the steiner problem in networks, Strongly polynomial algorithm for two special minimum concave cost network flow problems, A branch-and-price algorithm for switch-box routing, Maximum-Stopping-Value Policies in Finite Markov Population Decision Chains, Approximation algorithms for general one-warehouse multi-retailer systems, A branch-and-price algorithm for the Steiner tree packing problem., Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Minimum-weight two-connected spanning networks, Minimal-cost network flow problems with variable lower bounds on arc flows, An improved branch and bound algorithm for minimum concave cost network flow problems, A survey of dynamic network flows, Capacitated lot-sizing with extensions: a review, Polynomially solvable special cases of the Steiner problem in planar networks, The role of Steiner hulls in the solution to Steiner tree problems, Two new criteria for finding Steiner hulls in Steiner tree problems, The point-to-point delivery and connection problems: Complexity and algorithms, Steiner trees with \(n\) terminals among \(n+1\) nodes, Global search algorithms for minimum concave-cost network flow problems, Algorithms for the single-source uncapacitated minimum concave-cost network flow problem, On obstructions to small face covers in planar graphs, Minimal connected enclosures on an embedded planar graph, An algorithm for a concave production cost network flow problem, Two-edge connected spanning subgraphs and polyhedra, A Lagrangean heuristic for the capacitated concave minimum cost network flow problem, On perfectly two-edge connected graphs, On finding two-connected subgraphs in planar graphs, A simplex algorithm for a class of Leontief flow problems, Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm, Gainfree Leontief substitution flow problems, 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, Uncapacitated point-to-multipoint network flow problem and its application to multicasting in telecommunication networks, Packing Steiner trees: A cutting plane algorithm and computational results, Shortest paths algorithms: Theory and experimental evaluation, Perspectives of Monge properties in optimization, Improved Steiner tree algorithms for bounded treewidth, Faster algorithm for optimum Steiner trees, A math-heuristic Dantzig-Wolfe algorithm for capacitated lot sizing, Minimum concave-cost network flow problems: Applications, complexity, and algorithms, Minimum concave cost flow over a grid network, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Complexity and algorithms for nonlinear optimization problems, A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems, \(k\)-edge connected polyhedra on series-parallel graphs, Critical extreme points of the 2-edge connected spanning subgraph polytope, On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid, The complexity of welfare maximization in congestion games, On Directed Steiner Trees with Multiple Roots, A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface, On the Steiner 2-edge connected subgraph polytope, Unnamed Item