Send-and-Split Method for Minimum-Concave-Cost Network Flows
From MaRDI portal
Publication:3820348
DOI10.1287/moor.12.4.634zbMath0667.90036OpenAlexW2150855695MaRDI 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 networksdynamic economic-order-quantity problemminimum-additive-concave-cost nonnegative network flowssend-and-split method
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39)
Related Items
A branch-and-price algorithm for switch-box routing, Two-edge connected spanning subgraphs and polyhedra, The complexity of welfare maximization in congestion games, A Lagrangean heuristic for the capacitated concave minimum cost network flow problem, A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface, On Directed Steiner Trees with Multiple Roots, Approximation algorithms for general one-warehouse multi-retailer systems, On perfectly two-edge connected graphs, On finding two-connected subgraphs in planar graphs, Packing Steiner trees: A cutting plane algorithm and computational results, Shortest paths algorithms: Theory and experimental evaluation, Extending the kernel for planar Steiner tree to the number of Steiner vertices, A simplex algorithm for a class of Leontief flow problems, Perspectives of Monge properties in optimization, A robust optimization model for distribution network design under a mixed integer set of scenarios, Improved Steiner tree algorithms for bounded treewidth, Solving Steiner trees: Recent advances, challenges, and perspectives, Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible, Faster algorithm for optimum Steiner trees, Box-total dual integrality and edge-connectivity, Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm, Minimal-cost network flow problems with variable lower bounds on arc flows, Unnamed Item, A survey of dynamic network flows, Strategyproof auction mechanisms for network procurement, Capacitated lot-sizing with extensions: a review, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Strong Steiner Tree Approximations in Practice, Polynomially solvable special cases of the Steiner problem in planar networks, The role of Steiner hulls in the solution to Steiner tree problems, A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs, A dynamic programming approach for the pipe network layout problem, A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, Two new criteria for finding Steiner hulls in Steiner tree problems, An Exact Algorithm for the Steiner Forest Problem, The point-to-point delivery and connection problems: Complexity and algorithms, Steiner trees with \(n\) terminals among \(n+1\) nodes, A math-heuristic Dantzig-Wolfe algorithm for capacitated lot sizing, An improved branch and bound algorithm for minimum concave cost network flow problems, A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs, 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, Complexity and algorithms for nonlinear optimization problems, Unnamed Item, On the Steiner 2-edge connected subgraph polytope, A branch-and-price algorithm for the Steiner tree packing problem., Minimum concave-cost network flow problems: Applications, complexity, and algorithms, A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems, Minimum-weight two-connected spanning networks, 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, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid, Minimal connected enclosures on an embedded planar graph, Probabilistic analysis of an lp relaxation bound for the steiner problem in networks, \(k\)-edge connected polyhedra on series-parallel graphs, Maximum-Stopping-Value Policies in Finite Markov Population Decision Chains, An algorithm for a concave production cost network flow problem, Minimum concave cost flow over a grid network, Unnamed Item, Critical extreme points of the 2-edge connected spanning subgraph polytope, Strongly polynomial algorithm for two special minimum concave cost network flow problems, Uncapacitated point-to-multipoint network flow problem and its application to multicasting in telecommunication networks
