Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
From MaRDI portal
Publication:5929137
DOI10.1016/S0167-6377(00)00059-6zbMath1096.90543MaRDI QIDQ5929137
S. Thomas McCormick, Akiyoshi Shioura
Publication date: 2001
Published in: Operations Research Letters (Search for Journal in Brave)
Linear programming problem; Minimum cost flow; minimum cost tension; Minimum ratio cycle; Negative cycle canceling algorithm; Unimodular linear space
90C35: Programming involving graphs or networks
90C60: Abstract computational complexity for mathematical programming problems
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
Related Items
The MA-ordering max-flow algorithm is not strongly polynomial for directed networks, A new approach for computing a most positive cut using the minimum flow algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- Geometric algorithms and combinatorial optimization
- Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow
- A polynomial combinatorial algorithm for generalized minimum cost flow
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Finding minimum-cost circulations by canceling negative cycles
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- A new approach to the maximum-flow problem
- Note on Weintraub’s Minimum-Cost Circulation Algorithm
- Theoretical Efficiency of the Algorithm “Capacity” for the Maximum Flow Problem
- The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
- A Primal Algorithm to Solve Network Flow Problems with Convex Costs
- Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications
- More pathological examples for network flow problems
- 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
