Two strongly polynomial cut cancelling algorithms for minimum cost network flow
From MaRDI portal
Publication:689972
DOI10.1016/0166-218X(93)90025-JzbMath0801.90037OpenAlexW2060088365MaRDI QIDQ689972
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
Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)
Related Items
Computing maximum mean cuts, How to compute least infeasible flows, Fractional 0-1 programming: applications and algorithms, A faster strongly polynomial time algorithm to solve the minimum cost tension problem, A combinatorial cut-toggling algorithm for solving Laplacian linear systems, 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, 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, Minimax inverse problems of minimum cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- A strongly polynomial minimum cost circulation algorithm
- Scaling algorithms for network problems
- On the computational behavior of a polynomial-time network flow algorithm
- Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
- A characterization of the minimum cycle mean in a digraph
- The auction algorithm: A distributed relaxation method for the assignment problem
- Parallel concepts in graph theory
- Computing maximum mean cuts
- Monotone networks
- Finding Minimum-Cost Circulations by Successive Approximation
- Faster algorithms for the shortest path problem
- Finding minimum-cost circulations by canceling negative cycles
- A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
- Sensitivity theorems in integer linear programming
- An O (n 2 (m + N log n )log n ) min-cost flow algorithm
- A new approach to the maximum-flow problem
- Improved Time Bounds for the Maximum Flow Problem
- An Out-of-Kilter Method for Minimal-Cost Flow Problems
- The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Diagonal similarity and equivalence for matrices over groups with 0
- Reducing Matching to Polynomial Size Linear Programming
- A Fast Parametric Maximum Flow Algorithm and Applications
- Canceling most helpful total cuts for minimum cost network flow
- A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
- Depth-First Search and Linear Graph Algorithms
