Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow

DOI10.1287/moor.25.1.76.15208zbMath0977.90077OpenAlexW2006228567MaRDI QIDQ2757624

Satoru Iwata, S. Thomas McCormick, Maiko Shigeno

Publication date: 26 November 2001

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

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

zbMATH Keywords

scalingminimum cost flowcut cancelingcycle cancelingrelaxed optimality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

\(n\)-step cycle inequalities: facets for continuous multi-mixing set and strong cuts for multi-module capacitated lot-sizing problem ⋮ Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks ⋮ A new approach for computing a most positive cut using the minimum flow algorithms

This page was built for publication: Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow