The MA-ordering max-flow algorithm is not strongly polynomial for directed networks.
Akiyoshi ShiouraPublished in: Oper. Res. Lett. (2004)
Keyphrases
- max flow
- strongly polynomial
- computational complexity
- linear programming
- optimal solution
- min cost
- maximum flow
- combinatorial optimization
- simulated annealing
- mathematical model
- dynamic programming
- random walk
- linear program
- worst case
- knapsack problem
- graph structure
- execution times
- scheduling problem
- minimum cost flow
- np hard
- objective function