A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows.¶
Orlin, J. B. (1997). A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows. Mathematical Programming, 109-129.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Domain-specific¶
- Network Simplex Algorithm
- … proved polynomial time for a qualifying cost-scaling primal network-simplex variant built around a premultiplier rule, with $O(\min\{nm\log(nC),nm^2\log n\})$ pivots and $O(\min\{n^2m\log(nC),n^2m^2\log n\})$ time under the paper's parameterization; that result must not be generalized to arbitrary entering-arc rules.
This sourceEstablishes the polynomial cost-scaling premultiplier variant and its pivot/time bounds; it does not claim the same bound for every pivot rule.
- … proved polynomial time for a qualifying cost-scaling primal network-simplex variant built around a premultiplier rule, with $O(\min\{nm\log(nC),nm^2\log n\})$ pivots and $O(\min\{n^2m\log(nC),n^2m^2\log n\})$ time under the paper's parameterization; that result must not be generalized to arbitrary entering-arc rules.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:53192794aecc · see in the full table