The abstract talks about ϵ-approximation for m edges in O(m^(1+o(1))ϵ^−2). If this algorithm is practical that would be quite a speed up!