A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow

DOI10.1287/MOOR.27.3.445.313MaRDI QIDQ5704090zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Recommendations

• A polynomial combinatorial algorithm for generalized minimum cost flow
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Combinatorial approximation algorithms for generalized flow problems
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Faster algorithms for the generalized network flow problem

Cited in

(17)

• A generalized approximation framework for fractional network flow and packing problems
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Combinatorial interior point methods for generalized network flow problems
• A polynomial combinatorial algorithm for generalized minimum cost flow
• On circuit diameter bounds via circuit imbalances
• A simple GAP-canceling algorithm for the generalized maximum flow problem
• A POLYNOMIAL-TIME ALGORITHM FOR THE GENERALIZED INDEPENDENT-FLOW PROBLEM
• A strongly polynomial algorithm for generalized flow maximization
• On circuit diameter bounds via circuit imbalances
• Stochastic production-distribution planning with transportation mode-dependent lead times
• Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
• 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
• Solving integer minimum cost flows with separable convex cost objective polynomially
• scientific article; zbMATH DE number 437576 (Why is no real title available?)
• Monotonizing linear programs with up to two nonzeroes per column
• New polynomial-time cycle-canceling algorithms for minimum-cost flows

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704090)