# Variant of bipartite matching, with real capacities from source and to sink, all others unlimited

I've got a variant of bipartite graph matching and I can't find any literature about it.

We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real capacity edges from right vertices to sink (also summing to 1), and unlimited capacity edges between left and right. What is the fastest algorithm for max flow here?

To phrase it more colorfully, you have N types of dog food, totaling 1 kilogram; and N dogs, with each dog being able to eat a maximum quantity of food, but in total they can eat 1 kilogram. Not all dogs will eat all types of dog food, but they will eat up to their "capacity" of any combination of the types that they do like. How do you get the largest quantity of dog food fed to your dogs?

So far it looks like Edmonds-Karp is actually faster than push-relabel. I've been using the networkx python package implementation of both of these algorithms, but now I need to optimize for speed. I will be implementing a solution in C or Cython, but I'm concerned about the algorithm itself. It feels like there should be a specialized solution for this that works faster. Does anyone have any ideas?

• Did you try linear programming algorithm? If there is a library implementing LP algorithms you could compare LP performance with Edmonds-Karp or push-relabel algorithms. Just an idea. Jul 5, 2017 at 23:12
• I suppose you could try the algorithms listed here: en.wikipedia.org/wiki/Maximum_flow_problem#Solutions, and see which seems fastest. Or you could try to analyze their running time on graphs of the form you listed. Some of them might be primarily of theoretical interest and too complicated to be worth implementing.
– D.W.
Jul 6, 2017 at 0:06