Algorithm for Minimum Cost Ratio Cycle
Let G be a directed graph, let cost and profit
be two cost function on the edges of G. Edge costs and profits
may be positive or negative, but there must not exist cycles of non-positive
cost with respect to both cost and profit.
A minimum cost ratio cycle C is a cycle in G such that the ratio
cost(C)/profit(C) is minimum among all cycles in G.
MINIMUM_RATIO_CYCLE() computes a minimum cost ratio
cycle C (if there are no cycles of cost zero or less in G).
Example of How to Use MINIMUM_RATIO_CYCLE()
Tip
This algorithm is mainly of theoretical interest.
|