Abstract:

The problem of computing maximum flows and maximum bipartite matchings have been classical problems in theoretical computer science since the earliest days of computer science.  It is well-known that computing maximum flows in directed graphs is harder than computing maximum flows in undirected graphs, and harder than computing bipartite matchings, as there are well-known reductions from the undirected max flow and bipartite matching problem to the directed max flow problem.  Although it is unclear how much more difficult the directed max flow problem is, in this talk, I show that the directed maximum flow problem is not too much more difficult than the undirected max flow and the bipartite matching problem. In particular, I show that there exists a reduction from the directed max flow problem to the undirected max flow problem, and to the bipartite matching problem.  In the reduction from directed max flow to undirected max flow, we also derive a new algorithm for computing maximum flows in directed graphs, which has better running time guarantees than all previous known maximum flow algorithms for graphs with small imbalance, where the imbalance of a graph is defined to be the sum over all nodes v, | indegree(v) - outdegree(v) |.

Short Bio:

Henry Lin is a Ph.D. student studying theoretical computer science under the direction of professors Christos Papadimitriou and Satish Rao at UC Berkeley. Prior to attending UC Berkeley, Henry completed his B.S. degree at Cornell University and completed his senior research project under the direction of professors Eva Tardos and Tim Roughgarden.  His prior work includes work on network routing, network flow, and bipartite matching problems.