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 problemMinimum cost flowminimum cost tensionMinimum ratio cycleNegative cycle canceling algorithmUnimodular linear space

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (7)

On circuit diameter bounds via circuit imbalances ⋮ Solving MIPs via scaling-based augmentation ⋮ 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 ⋮ The subset assignment problem for data placement in caches ⋮ Improved Primal Simplex: A More General Theoretical Framework and an Extended Experimental Analysis ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

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

This page was built for publication: Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks