Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks

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)

zbMATH Keywords

Linear programming problem; Minimum cost flow; minimum cost tension; Minimum ratio cycle; Negative cycle canceling algorithm; Unimodular linear space

Mathematics Subject Classification ID

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, Improved Primal Simplex: A More General Theoretical Framework and an Extended Experimental Analysis

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item