Approximating the Girth
This paper considers the problem of computing a minimum weight cycle in weighted undirected graphs. Given a weighted undirected graph <i>G</i>(<i>V,E,w</i>), let <i>C</i> be a minimum weight cycle of <i>G</i>, let <i>w</i>(<i>C</i>) be the weight of <i>C</i> and let <i>w</i><sub><i>max</i></sub> (<i>C</i>) be the weight of the maximal edge of <i>C</i>. We obtain three new approximation algorithms for the minimum weight cycle problem:
 1. For integral weights from the range [1, <i>M</i>] an algorithm that reports a cycle of weight at most 4/3<i>w</i>(<i>C</i>) in <i>O</i>(<i>n</i><sup>2</sup> log <i>n</i>(log <i>n</i> + log <i>M</i>)) time.
 2. For integral weights from the range [1, <i>M</i>] an algorithm that reports a cycle of weight at most <i>w</i>(<i>C</i>) + <i>w</i><sub><i>max</i></sub> (<i>C</i>) in <i>O</i>(<i>n</i><sup>2</sup> log <i>n</i>(log <i>n</i> + log <i>M</i>)) time.
 3. For non-negative real edge weights an algorithm that for any ε > 0 reports a cycle of weight at most (4/3 + ε)<i>w</i>(<i>C</i>) in <i>O</i>(1/ε <i>n</i><sup>2</sup> log <i>n</i>(log log <i>n</i>)) time.
 In a recent breakthrough Vassilevska Williams and Williams [WW10] showed that a subcubic algorithm that computes the exact minimum weight cycle in undirected graphs with integral weights from the range [1, <i>M</i>] implies a subcubic algorithm for computing all-pairs shortest paths in directed graphs with integral weights from the range [− <i>M, M</i>]. This implies that in order to get a subcubic algorithm for computing a minimum weight cycle we have to relax the problem and to consider an approximated solution.
 Lingas and Lundell [LL09] were the first to consider approximation in the context of minimum weight cycle in weighted graphs. They presented a 2-approximation algorithm for integral weights with <i>O</i>(<i>n</i><sup>2</sup> log <i>n</i>(log <i>n</i> + log <i>M</i>)) running time. They also posed as an open problem the question whether it is possible to obtain a subcubic algorithm with a <i>c</i>-approximation, where <i>c</i> < 2. The current paper answers this question in the affirmative, by presenting an algorithm with 4/3-approximation and the same running time.
 Surprisingly, the approximation factor of 4/3 is not accidental. We show using the new result of Vassilevska Williams and Williams [WW10] that a subcubic combinatorial algorithm with (4/3 − ε)-approximation, where 0 < ε ≤ 1/3, implies a subcubic combinatorial algorithm for multiplying two boolean matrices.