A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow

DOI10.1287/moor.27.3.445.313zbMath1082.90507OpenAlexW2071419879MaRDI QIDQ5704090

Kevin D. Wayne

Publication date: 11 November 2005

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3574

zbMATH Keywords

minimum cost flow, gain factor, generalized minimum cost flow, polynomial combinatorial algorithm, strongly polynomial approximation scheme

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

On circuit diameter bounds via circuit imbalances ⋮ Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains ⋮ Reformulation of the linear program for completely ergodic MDPs with average cost criteria ⋮ Shortest path and maximum flow problems in networks with additive losses and gains ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ A simple GAP-canceling algorithm for the generalized maximum flow problem

This page was built for publication: A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow