Two strongly polynomial cut cancelling algorithms for minimum cost network flow

DOI10.1016/0166-218X(93)90025-JzbMATH Open0801.90037OpenAlexW2060088365MaRDI QIDQ689972FDOQ689972

Authors: Thomas R. Ervolina, S. Thomas McCormick 

Publication date: 2 January 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90025-j

Recommendations

• On dual minimum cost flow algorithms (extended abstract)
• On dual minimum cost flow algorithms
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow
• A new strongly polynomial dual network simplex algorithm

zbMATH Keywords

minimum cost network flowstrongly polynomial algorithms

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• The auction algorithm: A distributed relaxation method for the assignment problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Depth-First Search and Linear Graph Algorithms
• Scaling algorithms for network problems
• Sensitivity theorems in integer linear programming
• Title not available (Why is that?)
• A characterization of the minimum cycle mean in a digraph
• Finding Minimum-Cost Circulations by Successive Approximation
• A new approach to the maximum-flow problem
• Diagonal similarity and equivalence for matrices over groups with 0
• A Fast Parametric Maximum Flow Algorithm and Applications
• Title not available (Why is that?)
• Parallel concepts in graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Faster algorithms for the shortest path problem
• A strongly polynomial minimum cost circulation algorithm
• On the computational behavior of a polynomial-time network flow algorithm
• Finding minimum-cost circulations by canceling negative cycles
• Title not available (Why is that?)
• Monotone networks
• Title not available (Why is that?)
• An O (n ² (m + N log n )log n ) min-cost flow algorithm
• Title not available (Why is that?)
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• Title not available (Why is that?)
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Computing maximum mean cuts
• Improved Time Bounds for the Maximum Flow Problem
• The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
• Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducing Matching to Polynomial Size Linear Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Canceling most helpful total cuts for minimum cost network flow

Cited In (20)

• Finding minimum-cost circulations by canceling negative cycles
• Title not available (Why is that?)
• A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow
• A new approach for computing a most positive cut using the minimum flow algorithms
• Fractional 0-1 programming: applications and algorithms
• An efficient network flow code for finding all minimum cost \(s-t\) cutsets
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• How to compute least infeasible flows
• An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
• A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
• Minimax inverse problems of minimum cuts
• A faster strongly polynomial time algorithm to solve the minimum cost tension problem
• New polynomial-time cycle-canceling algorithms for minimum-cost flows
• Computing maximum mean cuts
• Canceling most helpful total cuts for minimum cost network flow
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• A combinatorial cut-toggling algorithm for solving Laplacian linear systems
• Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow

This page was built for publication: Two strongly polynomial cut cancelling algorithms for minimum cost network flow

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