  Efficient computation of shortest cycles which form a homology basis under
$\mathbb{Z}_2$-additions in a given simplicial complex $\mathcal{K}$ has been
researched actively in recent years. When the complex $\mathcal{K}$ is a
weighted graph with $n$ vertices and $m$ edges, the problem of computing a
shortest (homology) cycle basis is known to be solvable in $O(m^2n/\log n+
n^2m)$-time. Several works \cite{borradaile2017minimum, greedy} have addressed
the case when the complex $\mathcal{K}$ is a $2$-manifold. The complexity of
these algorithms depends on the rank $g$ of the one-dimensional homology group
of $\mathcal{K}$. This rank $g$ has a lower bound of $\Theta(n)$, where $n$
denotes the number of simplices in $\mathcal{K}$, giving an $O(n^4)$ worst-case
time complexity for the algorithms in \cite{borradaile2017minimum,greedy}. This
worst-case complexity is improved in \cite{annotation} to $O(n^\omega +
n^2g^{\omega-1})$ for general simplicial complexes where $\omega< 2.3728639$
\cite{le2014powers} is the matrix multiplication exponent. Taking
$g=\Theta(n)$, this provides an $O(n^{\omega+1})$ worst-case algorithm. In this
paper, we improve this time complexity. Combining the divide and conquer
technique from \cite{DivideConquer} with the use of annotations from
\cite{annotation}, we present an algorithm that runs in $O(n^\omega+n^2g)$ time
giving the first $O(n^3)$ worst-case algorithm for general complexes. If
instead of minimal basis, we settle for an approximate basis, we can improve
the running time even further. We show that a $2$-approximate minimal homology
basis can be computed in $O(n^{\omega}\sqrt{n \log n})$ expected time. We also
study more general measures for defining the minimal basis and identify
reasonable conditions on these measures that allow computing a minimal basis
efficiently.
