Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs Orlin's algorithm is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and the node sets of the graph $G(V, E)$ in question.

If the graph $G(V = V_1 \cup V_2, E)$ is known to be bipartite (with $V_1$ and $V_2$ denoting the "left" and "right" node sets), can one compute the minimum cost maximum flow any faster? Here the flow is between an additional source that is connected to the nodes in $V_1$ and an additional sink that is connected to the nodes in $V_2$.

I'm also interested to hear about algorithms that do not have better time complexity, but perform well in practice.

You can assume that all capacities and costs are non-negative integers. There can be both limited-capacity and unlimited-capacity edges in the graph. Also, assume that both the maximum non-infinite capacity $c$, and the maximum edge cost $w$ is small; i.e. one can consider both as $O(1)$ terms for complexity purposes. 

Thanks!

Edit: My current-best solution is to use a minimum cost augmentation algorithm, which solves the problem in $O(|E| \; F \log |V|)$ time, where $F$ is the value of the maximum flow. Since $F$ is bounded by $c \;|V|$ (which is $O(|V|)$ under our assumptions), this approach results in an overall time complexity of $O(|E| \; |V| \; \log |V|)$. Is it possible to beat this?
See this paper. I think adopting their technique, many(usually scaling based) min-cost flow algorithms with running time $O(f(n,m))$ can run in $O(f(n_1,m))$ time. Here $n_1$ is the size of the smaller bipartition.

If $f(n,m)$ is the best possible run time for min-cost flow on general graphs with $n$ vertices and $m$ edges. There is an easy argument that you can't expect anything running in $o(f(n_1,m))$ time. (with some reasonable assumptions, like $n\leq m$, $f(n,cm)=O(f(n,m))$ for any constant $c$)

Proof: Otherwise, you can apply the standard vertex splitting operation to the input graph and use the bipartite min-cost flow algorithm and get a better running time. 

Finally, if you are restricting cost and capacities things, these scaling algorithms is still pretty much state of the art(difference is at most $\log c$ for w/e parameter $c$ you care about). You can decipher that Theorem 3.5 to see which one of them gives you the best result.