A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives
From MaRDI portal
Publication:2817799
DOI10.1137/140978296zbMath1410.91327arXiv1110.4882OpenAlexW2514746546MaRDI QIDQ2817799
Publication date: 2 September 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.4882
convex optimizationmarket equilibrium computationstrongly polynomial algorithmsnetwork flow algorithms
Convex programming (90C25) Quadratic programming (90C20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) General equilibrium theory (91B50) General topics in the theory of algorithms (68W01)
Related Items (8)
Iteratively reweighted least squares and slime mold dynamics: connection and convergence ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Market exchange models and geometric programming ⋮ Mean‐standard deviation model for minimum cost flow problem ⋮ The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential ⋮ Ascending-Price Algorithms for Unknown Markets ⋮ Complexity of linear minimization and projection on some sets ⋮ Decreasing minimization on base-polyhedra: relation between discrete and continuous cases
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A polynomial algorithm for minimum quadratic cost flow problems
- Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm
- Matrix multiplication via arithmetic progressions
- Eisenberg-Gale markets: algorithms and game-theoretic properties
- A strongly polynomial minimum cost circulation algorithm
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Geometric algorithms and combinatorial optimization.
- A capacity scaling algorithm for convex cost submodular flows
- Fast cycle canceling algorithms for minimum cost submodular flow
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- Complexity and algorithms for nonlinear optimization problems
- Improved algorithms for computing fisher's market clearing prices
- A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Spending Constraint Utilities with Applications to the Adwords Market
- Consensus of Subjective Probabilities: The Pari-Mutuel Method
- Market equilibrium via a primal--dual algorithm for a convex program
- Solving integer minimum cost flows with separable convex cost objective polynomially
- Submodular systems and related topics
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Combinatorial Optimization with Rational Objective Functions
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources
- Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
- Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications
- Minimizing a Convex Cost Closure Set
- Concave Generalized Flows with Applications to Market Equilibria
- Fibonacci heaps and their uses in improved network optimization algorithms
- A strongly polynomial algorithm for generalized flow maximization
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- The notion of a rational convex program, and an algorithm for the arrow-debreu Nash bargaining game
- On Convex Minimization over Base Polytopes
- Algorithmic Game Theory
- Convex separable optimization is not much harder than linear optimization
This page was built for publication: A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives
