Min cost max flow in bipartite run time

I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).

For the sake of my question, denote $n=|E|$.

Are there algorithms that will run in $O(n^2)$, or even $O(n\log(n))$, or for that matter anything less than $O(n^3)$? In my case, $n$ is ~100,000, so $O(n^3)$ is impractical for me.

'Extra' questions (should these go under a separate question?):

• Do any of these supper multi-graphs (I have 2 edges from my super-source node to each of the "blue" nodes in my bipartite graph, and 2 edges from each of the "red" nodes to my super-sink node)?

• Are there efficient implementations of such algorithms (that run in less than $O(n^3)$, and support multi-graphs) in C++, C, or Python?

• If the answer is 'no', what are popular approximation algorithms and their associated run times?

Assuming your edges have unit capacity, but non-unit costs, you can reduce this to a maximum-weight bipartite matching, that is, the assignment problem. For this, just make a copy of each vertex. The assignment problem can be solved in $O(n^{1.5})$ time.

StackExchange Computer Science Q#6234, answer score: 2