of $G$ we invoke this procedure for every $r=(1+\epsilon)^i$ for $1\leq i \leq
\log_{1+\epsilon}{n W}$ and stop once the procedure returns a cycle. If $g$ is the girth of $G$ this incurs an additional $\log_{1+\epsilon}{g}$ factor to the running time (as for the first index $i$ such that $(1+\epsilon)^i >g$ the algorithm will return a cycle w.h.p.) and an additional $(1+\epsilon)$ factor in the approximation ratio. The additional $(1+\epsilon)$ factor in the approximation ratio can be avoided if the weights are integers by simply using binary search on the range between 1 and $nW$ (where $W$ is the maximum edge weight in $G$) and finding two consecutive integers $i$ and $i+1$ such that the procedure returned a cycle of length at most $3(i+1)$ when invoked on $i+1$ but not a cycle when invoked on $i$. This incurs a $\log{nW}$ factor in the running time that can be improved to $O(\log{n})$ by the same method as done in [@PRSTV18] of contracting small weight strongly connected components and deleting large weight edges (see Section 5.1 in [@PRSTV18] for more details).

Let $G =(V,E)$ be a directed graph with $n$ vertices and $m$ edges. We assume the graph $G$ is of average degree 