Bounds on the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows
Philip N. Klein, Serge A. Plotkin, Satish S. Rao, Éva Tardos · 1993
The most well-known theorem in combinatorial optimization is the classical max-flow min-cut theorem of Ford and Fulkerson. This theorem serves as the basis for deriving efficient algorithms for finding max-flows and min-cuts. Starting with the work of Leighton and Rao, significant effort was directed towards finding approximate analogs for the undirected multicommodity flow problem. In this paper we consider an approximate max-flow min-cut theorem for directed graphs. We prove a polylogarithmic bound on the worst case ratio between the minimum multicut and the value of the maximum multicommodity flow in the special case when the demands are symmetric. The method presented in this paper can be used to give polynomial time polylogarithmic approximation algorithms for the corresponding minimum directed multicut problems. The problem with symmetric demands extends the only previously known special case concerning directed graphs due to Leighton and Rao, who proved an O(log n) bound for th...