Finding minimum cost to time ratio cycles with small integral transit times
Mark E. Hartmann, James B. Orlin · Networks · 1993
Abstract Let D = (V, E) be a digraph with n vertices and m arcs. For each e ∈ E there is an associated cost ce and a transit time te; ce can be arbitrary, but we require te to be a non‐negative integer. The cost to time ratio of a cycle C is Λ(C) = ∑e∈cce/∑e∈c. Let E' ⊆ E denote the set of arcs e with te > 0, let Tu = max{tuv: (u, v) ∈ E} for each vertex u, and let T = ∑u∈v Tu. We give a new algorithm for finding a cycle C with the minimum cost to time ratio Λ(C). The algorithm's O(T(m + n lo g 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(n2) 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 te = 1 for all e ∈ 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. © 1993 by John Wiley & Sons, Inc.