Note on Weintraub’s Minimum-Cost Circulation Algorithm

DOI10.1137/0218039MaRDI QIDQ3829324zbMATH OpenOpenAlexFDO

Authors Francisco Barahona, Éva Tardos

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218039

zbMATH Keywords

maximum flowaugmenting pathpolynomial timescalingresidual graphconvex cost functionlinear objective functionminimum-cost circulation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Recommendations

• scientific article; zbMATH DE number 3900474
• A strongly polynomial minimum cost circulation algorithm
• Finding Minimum-Cost Circulations by Successive Approximation
• Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
• An O (n ² (m + N log n )log n ) min-cost flow algorithm

Cited in

(9)

• Inapproximability of shortest paths on perfect matching polytopes
• Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
• Minimum-cost flow algorithms: an experimental evaluation
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• How to compute least infeasible flows
• Pivot rules for circuit-augmentation algorithms in linear optimization
• Maximum utility product pricing models and algorithms based on reservation price
• Inapproximability of shortest paths on perfect matching polytopes
• New polynomial-time cycle-canceling algorithms for minimum-cost flows

This page was built for publication: Note on Weintraub’s Minimum-Cost Circulation Algorithm

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