FINDING MINIMUM-COST TO TIME RATIO CYCLES WITH SMALL INTEGRAL TRANSIT TIMES

Let D = (V, E) be a digraph with n vertices and m arcs. For each e is-an-element-of E there is an associated cost c(e) and a transit time t(e); c(e) can be arbitrary, but we require t(e) to be a non-negative integer. The cost to time ratio of a cycle C is lambda(C) = SIGMA(e is-an-element-of C) C(e)/SIGMA(e is-an-element-of C) t(e). Let E' subset-or-equal-to E denote the set of arcs e with t(e) > 0, let T(u) = max{t(uv): (u, v) is-an-element-of E} for each vertex u, and let T = SIGMA(u is-an-element-of V) T(u). We give a new algorithm for finding a cycle C with the minimum cost to time ratio lambda(C). The algorithm's O(T(m + n log n)) running time is dominated by O(T) shortest paths calculations on a digraph with non-negative arc lengths. Further, we consider early termination of the algorithm and a faster O(Tm) algorithm in case E - E' is acyclic, i.e., in case each cycle has a strictly positive transit time, which gives an O(n 2) algorithm for a class of cyclic staffing problems considered by Bartholdi et al. The algorithm can be seen to be an extension of the O(nm) algorithm of Karp for the case in which t(e) = 1 for all e is-an-element-of E, which is the problem of calculating a minimum mean cycle. Our algorithm can also be modified to solve the related parametric shortest paths problem in O(T(m + n log n)) time. (C) 1993 by John Wiley & Sons, Inc.