Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs

DOI10.1287/moor.2021.1151zbMath1492.90180OpenAlexW3198977613MaRDI QIDQ5076726

Philipp Warode, Max Klimm

Publication date: 17 May 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2021.1151

zbMATH Keywords

computational complexityparametric flowgraph LaplacianWardrop equilibriumparametric quadratic program

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Quadratic programming (90C20) Sensitivity, stability, parametric optimization (90C31) Games with infinitely many players (91A07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computation of the Nash equilibrium selected by the tracing procedure in \(N\)-person games
• Structural and algorithmic properties for parametric minimum cuts
• A polynomial algorithm for minimum quadratic cost flow problems
• A parametric algorithm for convex cost network flow and related problems
• Homotopy methods to compute equilibria in game theory
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• Parametric shortest path algorithms with an application to cyclic staffing
• On the geometry and Laplacian of a graph
• Laplacian matrices of graphs: A survey
• Topology of series-parallel networks
• A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Non-linear network problems
• A Full Analytical Implementation of the PARTAN/Frank–Wolfe Algorithm for Equilibrium Assignment
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Solving integer minimum cost flows with separable convex cost objective polynomially
• Improved Efficiency of the Frank-Wolfe Algorithm for Convex Network Programs
• Updating the Inverse of a Matrix
• A decomposition algorithm for quadratic programming
• Computational complexity of parametric linear programming
• The polynomial solvability of convex quadratic programming
• An Extension of Lemke’s Method to the Piecewise Linear Complementarity Problem
• Origin-Based Algorithm for the Traffic Assignment Problem
• The Simplex Algorithm Is NP-Mighty
• Computing network tolls with support constraints
• A Fast Parametric Maximum Flow Algorithm and Applications
• A bad network problem for the simplex method and other minimum cost flow algorithms
• Methods for Modifying Matrix Factorizations
• Algorithmic results for potential‐based flows: Easy and hard cases
• Computing all Wardrop Equilibria parametrized by the Flow Demand
• Solving SDD linear systems in nearly m log ^1/2 n time
• Equilibrium Points of Bimatrix Games
• Stochastic Shortest Paths Via Quasi-convex Maximization
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• An Algorithm for Solving Nonlinear Resistor Networks
• Über ein Paradoxon aus der Verkehrsplanung
• Nonlinear networks. IIa
• Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix

This page was built for publication: Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs