Finding minimum cost to time ratio cycles with small integral transit times

Abstract

Abstract Let D = (V, E) be a digraph with n vertices and m arcs. For each e ∈ 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 Λ (C) = ∑ e ∈ c c e /∑ e ∈ c . Let E' ⊆ E denote the set of arcs e with t e > 0, let T u = max{ t uv : (u, v) ∈ E } for each vertex u , and let T = ∑ u ∈ v T u . 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 ( 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 ∈ 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.