A polynomial algorithm for minimum quadratic cost flow problems

DOI10.1016/0377-2217(84)90160-7zbMath0555.90039OpenAlexW1977895455MaRDI QIDQ761341

Michel Minoux

Publication date: 1984

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(84)90160-7

zbMATH Keywords

polynomial algorithmscaling techniquequaratic separable costs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Deterministic network models in operations research (90B10)

Related Items

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, Application of the dual active set algorithm to quadratic network optimization, 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, Collusion in atomic splittable routing games, Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs, Error minimization methods in biproportional apportionment, Scheduling for electricity cost in a smart grid, Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm, Efficient methods for selfish network design, Selfish splittable flows and NP-completeness, A survey on the continuous nonlinear resource allocation problem, Implementing an “exact” Newton method for separable convex transportation problems, Complexity and algorithms for nonlinear optimization problems, A proximal subgradient projection algorithm for linearly constrained strictly convex problems, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, New algorithms for convex cost tension problem with application to computer vision, Unnamed Item, Scheduling for Electricity Cost in Smart Grid

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum norm problems over transportation polytopes
• The ellipsoid method and its consequences in combinatorial optimization
• A Method of Solution for Quadratic Programs
• A reduced subgradient algorithm
• An operator theory of parametric programming for the transportation problem-I
• The Simplex Method for Quadratic Programming
• Dealing with degeneracy in reduced gradient algorithms
• A polynomially bounded algorithm for a singly constrained quadratic program
• Feature Article—The Ellipsoid Method: A Survey
• On the convergence of a block successive over-relaxation method for a class of linear complementarity problems
• Optimal Routing in a Packet-Switched Computer Network
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Cost operator algorithms for the transportation problem
• An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems
• Estimating Nonnegative Matrices from Marginal Data
• The Lattice Point Covering Theorem for Rectangles