A polynomial algorithm for minimum quadratic cost flow problems
From MaRDI portal
Network flow problems with quaratic separable costs appear in a number of important applications such as approximating input-output matrices in economy, projecting and forecasting traffic matrices in telecommunication networks, or solving nondifferentiable cost flow problems by subgradient algorithms. Extending a scaling technique, used in the case of linear cost flows, to quadratic cost flows, a polynomial algorithm for this class of problems is given.
Recommendations
- Solving integer minimum cost flows with separable convex cost objective polynomially
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- Finding minimum-cost flows by double scaling
- An algorithm for solving quadratic network flow problems
- Parametric computation of minimum-cost flows with piecewise quadratic costs
Cites work
- A method of solution for quadratic programs
- A polynomially bounded algorithm for a singly constrained quadratic program
- A reduced subgradient algorithm
- An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems
- An operator theory of parametric programming for the transportation problem-I
- Cost operator algorithms for the transportation problem
- Dealing with degeneracy in reduced gradient algorithms
- Estimating Nonnegative Matrices from Marginal Data
- Feature Article—The Ellipsoid Method: A Survey
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3871019 (Why is no real title available?)
- scientific article; zbMATH DE number 3664705 (Why is no real title available?)
- scientific article; zbMATH DE number 3677572 (Why is no real title available?)
- scientific article; zbMATH DE number 3783030 (Why is no real title available?)
- scientific article; zbMATH DE number 3791941 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 3225808 (Why is no real title available?)
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Minimum norm problems over transportation polytopes
- 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
- The ellipsoid method and its consequences in combinatorial optimization
- The Lattice Point Covering Theorem for Rectangles
- The Simplex Method for Quadratic Programming
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Cited in
(26)- New algorithms for convex cost tension problem with application to computer vision
- An algorithm for solving quadratic network flow problems
- Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints
- Scheduling for electricity cost in a smart grid
- Error minimization methods in biproportional apportionment
- 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
- Preemptive benchmarking problem: An approach for official statistics in small areas
- Collusion in atomic splittable routing games
- A survey on the continuous nonlinear resource allocation problem
- Complexity and algorithms for nonlinear optimization problems
- A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
- Scheduling for electricity cost in smart grid
- Network flow methods for electoral systems
- Parametric maximum flow methods for minimax approximation of target quotas in biproportional apportionment
- Solving integer minimum cost flows with separable convex cost objective polynomially
- Implementing an “exact” Newton method for separable convex transportation problems
- Efficient methods for selfish network design
- Selfish splittable flows and NP-completeness
- Parametric computation of minimum-cost flows with piecewise quadratic costs
- A proximal subgradient projection algorithm for linearly constrained strictly convex problems
- The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game
- Quadratic cost flow and the conjugate gradient method
- Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm
- A fast polynomial time algorithm for logistics network flows
This page was built for publication: A polynomial algorithm for minimum quadratic cost flow problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q761341)
