We present two new algorithms to compute an approximate minimum cycle basis. For any integer k ≥ 1, we give (2k − 1)-approximation algorithms with expected running time O(k m n^{1 + 2/}^{k} + m n^{(1 + 1/}^{k}^{)(}^{ω}^{ − 1)}) and deterministic running time O( n^{3 + 2/}^{k} ), respectively. Here ω is the best exponent of matrix multiplication. It is presently known that ω < 2.376. Both algorithms are o( m^{ω}) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Θ(m^{ω}) bound. We also present a 2-approximation algorithm with expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n^{3}) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.
BibTeX Entry: