Solving integer minimum cost flows with separable convex cost objective polynomially
From MaRDI portal
Publication:3716775
DOI10.1007/BFb0121104zbMath0588.90027OpenAlexW2156347727MaRDI QIDQ3716775
Publication date: 1986
Published in: Mathematical Programming Studies (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bfb0121104
polynomial algorithmminimum cost network flowout-of-kilter methodnonlinear network flowsintegrality restrictons on the flowsscaling approachseparable convex cost functions on the arcs
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Quadratic programming (90C20) Deterministic network models in operations research (90B10)
Related Items (26)
Optimal deterministic and robust selection of electricity contracts ⋮ A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks ⋮ Network flow methods for electoral systems ⋮ Parametric maximum flow methods for minimax approximation of target quotas in biproportional apportionment ⋮ Preemptive benchmarking problem: An approach for official statistics in small areas ⋮ Local optimality conditions for multicommodity flow problems with separable piecewise convex costs ⋮ A capacity scaling algorithm for convex cost submodular flows ⋮ Disruption management in production planning ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Error minimization methods in biproportional apportionment ⋮ Incremental subgradient algorithms with dynamic step sizes for separable convex optimizations ⋮ Scheduling for electricity cost in a smart grid ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ Using quadratic programming to solve high multiplicity scheduling problems on parallel machines ⋮ A polynomial algorithm for an integer quadratic non-separable transportation problem ⋮ Graver basis and proximity techniques for block-structured separable convex integer minimization problems ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ Maximum network flows with concave gains ⋮ Use of primal-dual technique in the network algorithm for two-way contingency tables ⋮ A Polynomial-Time Descent Method for Separable Convex Optimization Problems with Linear Constraints ⋮ A capacity scaling algorithm for the constrained maximum flow problem ⋮ Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ Discrete convex analysis ⋮ Permutohedra and minimal matrices ⋮ Scheduling for Electricity Cost in Smart Grid
This page was built for publication: Solving integer minimum cost flows with separable convex cost objective polynomially
