Speaker: Haim Kaplan (Tel Aviv University, Israel)

Abstract

We consider the minimum cost flow problem on graphs with unit capacities and its special cases. In previous studies, special purpose algorithms exploiting the fact that capacities are one have been developed. In contrast, for maximum flow with unit capacities, the best bounds are proven for slight modifications of classical blocking flow and push-relabel algorithms.

We show that the classical cost scaling algorithms of Goldberg and Tarjan (for general integer capacities) applied to a problem with unit capacities achieve or improve the best known bounds. For weighted bipartite matching we establish a bound of $O(\sqrt{r}m\log C)$ on a slight variation of this algorithm. Here $r$ is the size of the smaller side of the bipartite graph, $m$ is the number of edges, and $C$ is the largest absolute value of an arc-cost. This simplifies a result of Duan et al and improves the bound, answering an open question of Tarjan and Ramshaw. For graphs with unit vertex capacities we establish a novel $O(\sqrt{n}m\log(nC))$ bound.

This better theoretical understanding of minimum cost flow on one hand, and recent extensive experimental work on algorithms for maximum flow on the other hand, calls for further engineering and experimental work on algorithms for minimum cost flow. I will discuss possible future research along these lines.