Algorithms for source-to-all maximum cost-to-time ratio problem in acyclic networks

The source-to-all maximum cost-to-time ratio problem is the problem of finding the maximum cost-to-time ratio path from a source node to every other node. The motivation comes from an application in large-scale linear programming. We present three algorithms for solving the problem. We give proofs of correctness and we analyze the running times. One of the algorithms is polynomial and the remaining two are pseudopolynomial. We present extensive computational results on several networks.