An exact solution for biclique vertex-cover problem on a bipartite graph
If you have an exact algorithm for the partitioning problem (perhaps one is mentioned in the paper describing the approximate algorithm?), you immediately have an exact algorithm for the covering problem.

First, observe that a partition is a valid cover.  Now suppose the partitioning algorithm reports an optimal partition with $k$ bicliques, and suppose to the contrary that there exists a cover $C$ with fewer than $k$ bicliques.  But any cover can be turned into a partition easily: Whenever two bicliques in the cover contain the same vertex, delete the vertex from one of them.  (This works because bicliques are hereditary: every induced subgraph of a biclique is also a biclique.)  This will result in a valid cover with at most as many bicliques as there were originally (it may cause a biclique to have zero vertices: In that case, the original cover was not minimal).  Repeat this vertex deletion step until all bicliques are pairwise vertex disjoint.  If we apply this to the cover $C$, then because we started with strictly fewer than $k$ bicliques and never increased the number of them that we have, we now have a partition with strictly fewer than $k$ bicliques, contradicting the known optimal solution from the partition solver.  Thus the optimal partition must have also been an optimal cover.