A polynomial combinatorial algorithm for generalized minimum cost flow
From MaRDI portal
Publication:2819530
DOI10.1145/301250.301261zbMath1345.90103OpenAlexW2087970026MaRDI QIDQ2819530
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/301250.301261
Programming involving graphs or networks (90C35) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Improving time bounds on maximum generalised flow computations by contracting the network ⋮ Minimal-cost network flow problems with variable lower bounds on arc flows ⋮ A least-squares minimum-cost network flow algorithm ⋮ The two variable per inequality abstract domain ⋮ Incremental closure for systems of two variables per inequality ⋮ Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks ⋮ A survey of very large-scale neighborhood search techniques ⋮ A cycle augmentation algorithm for minimum cost multicommodity flows on a ring
