  Given an $n$-vertex $m$-edge graph $G$ with non negative edge-weights, the
girth of $G$ is the weight of a shortest cycle in $G$. For any graph $G$ with
polynomially bounded integer weights, we present a deterministic algorithm that
computes, in $\tilde{\cal O}(n^{5/3}+m)$-time, a cycle of weight at most twice
the girth of $G$. Our approach combines some new insights on the previous
approximation algorithms for this problem (Lingas and Lundell, IPL'09; Roditty
and Tov, TALG'13) with Hitting Set based methods that are used for approximate
distance oracles and date back from (Thorup and Zwick, JACM'05). Then, we turn
our algorithm into a deterministic $(2+\varepsilon)$-approximation for graphs
with arbitrary non negative edge-weights, at the price of a slightly worse
running-time in $\tilde{\cal O}(n^{5/3}\log^{{\cal O}(1)}{(1/\varepsilon)}+m)$.
Finally, if we insist in removing the dependency in the number $m$ of edges, we
can transform our algorithms into an $\tilde{\cal O}(n^{5/3})$-time randomized
$4$-approximation for the graphs with non negative edge-weights -- assuming the
adjacency lists are sorted. Combined with the aforementioned Hitting Set based
methods, this algorithm can be derandomized, thereby yielding an $\tilde{\cal
O}(n^{5/3})$-time deterministic $4$-approximation for the graphs with
polynomially bounded integer weights, and an $\tilde{\cal O}(n^{5/3}\log^{{\cal
O}(1)}{(1/\varepsilon)})$-time deterministic $(4+\varepsilon)$-approximation
for the graphs with non negative edge-weights. To the best of our knowledge,
these are the first known subquadratic-time approximation algorithms for
computing the girth of weighted graphs.
