New polynomial-time cycle-canceling algorithms for minimum-cost flows

DOI10.1002/1097-0037(200008)36:1%3C53::AID-NET6%3E3.0.CO;2-YMaRDI QIDQ4509383zbMATH OpenOpenAlexFDO

Authors P. T. Sokkalingam, Ravindra K. Ahuja, James B. Orlin

Publication date 4 October 2001

Full work available at URL https://doi.org/10.1002/1097-0037(200008)36:1%3C53::aid-net6%3E3.0.co;2-y

zbMATH Keywords

convex cost-flow problemcycle-canceling algorithmminimum-cost flow problemnetwork flowsscaling algorithmsstrongly polynomial algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Complexity and performance of numerical algorithms (65Y20) Deterministic network models in operations research (90B10)

Recommendations

• Fast cycle canceling algorithms for minimum cost submodular flow
• A polynomial cycle canceling algorithm for submodular flows
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• A polynomial combinatorial algorithm for generalized minimum cost flow
• A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A POLYNOMIAL-TIME DUAL SIMPLEX ALGORITHM FOR THE MINIMUM COST FLOW PROBLEM
• A polynomial time primal network simplex algorithm for minimum cost flows
• A POLYNOMIAL TIME INTERIOR POINT ALGORITHM FOR MINIMUM COST FLOW PROBLEMS
• A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow

Cites work

• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Note on Weintraub’s Minimum-Cost Circulation Algorithm

Cited in

(16)

• Scheduling for electricity cost in a smart grid
• A minimum mean cycle cancelling method for nonlinear multicommodity flow problems
• The minimum mean cycle-canceling algorithm for linear programs
• A novel approach to subgraph selection with multiple weights on arcs
• Solving coalitional resource games
• Preemptive benchmarking problem: An approach for official statistics in small areas
• Combinatorial algorithms for the minimum interval cost flow problem
• Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow
• Scheduling for electricity cost in smart grid
• Minimum-cost flow algorithms: an experimental evaluation
• On dual minimum cost flow algorithms (extended abstract)
• Finding minimum-cost circulations by canceling negative cycles
• About the minimum mean cycle-canceling algorithm
• A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• Generalized minimal cost flow problem in fuzzy nature: an application in bus network planning problem

This page was built for publication: New polynomial-time cycle-canceling algorithms for minimum-cost flows

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