Send-and-Split Method for Minimum-Concave-Cost Network Flows
From MaRDI portal
Publication:3820348
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
capacitated networks; dynamic economic-order-quantity problem; minimum-additive-concave-cost nonnegative network flows; send-and-split method
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
Strong Steiner Tree Approximations in Practice, 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, Unnamed Item, A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs, A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, An Exact Algorithm for the Steiner Forest Problem, A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, Maximum-Stopping-Value Policies in Finite Markov Population Decision Chains, Approximation algorithms for general one-warehouse multi-retailer systems, Unnamed Item, A branch-and-price algorithm for the Steiner tree packing problem., Solving Steiner trees: Recent advances, challenges, and perspectives, 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, A dynamic programming approach for the pipe network layout problem, Valid inequalities for separable concave constraints with indicator variables, 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, Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible, Strategyproof auction mechanisms for network procurement, 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, A robust optimization model for distribution network design under a mixed integer set of scenarios, Box-total dual integrality and edge-connectivity, 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