<p>I can recommend my recent paper <a href="http://arxiv.org/abs/1110.6832">http://arxiv.org/abs/1110.6832</a> on multicommodity flows and cuts in polymatroidal networks; we generalize several known results in standard graphs. Although we do not give a nice table summary we discuss many of the known cases. Some of the results that are not discussed in the paper but are of relevance are those for planar undirected graphs and some special cases. These include the result of
Satish Rao on $O(\sqrt{\log n})$ bound on flow-cut gap and tight bound of $2$ for series-parallel graphs by Chakrabarti-Jaffe-Lee-Vincent and some others. James Lee has several papers on flows and cuts on these graphs and any relatively recent one will discuss the existing literature.</p>

CC BY-SA 3.0
2012-02-28T04:30:05.507Z
2012-02-28T04:30:05.507Z
Chandra Chekuri
<p>This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to cut (say, within a factor that is constant or polylogarithmic in the number of flows). Examples are:</p>

<p>1) Flow polytope (also called demand polytope) for multicommodity flow in undirected graphs is within O(log k) of cut as shown in </p>

<p>F. Leighton and S. Rao,“An approximate max-flow min-cut theoremfor uniform multicommodity flow problems with applications to approximation algorithms,” in Proc. of 28th Annual Symposium on Foundations of Computer Science, (Los Alamitos, California), 1988.</p>

<p>N. Linial, E. London, and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications,” Combinatorica, vol. 15, no. 2, pp. 215–245, 1995.</p>

<p>2) Demand polytope of multicommodity flow in directed graphs with symmetric demands is within O(log^2 k) of cut as shown in </p>

<p>P. Klein, S. Plotkin, S. Rao, and E. Tardos, “Bounds on the max-flow min-cut ratio for directed multicommodity flows,” J. Algorithms, no. 22, pp. 241–269, 1997.</p>

<p>3) Max sum-rate in groupcast is within a factor 2 of the multicut. (I don't know a reference for this result. Could someone help me with this? Thanks.)</p>

<p>I would like to know more such positive results affirming flow being close to cut assuming certain structure of the problem (such as undirectedness of graph or symmetric demands, as in above). It would be great if you can give me a one-line summary of the result(s) and a reference of the paper. Thanks.</p>

<ds.algorithms><approximation-algorithms><approximation-hardness><max-flow-min-cut><multicommodity-flow>
Request for references on multicommodity flow-cut results
user7823
# Request for references on multicommodity flow-cut results

(Asked by: username_0 on 2012-02-27)

This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to cut (say, within a factor that is constant or polylogarithmic in the number of flows). Examples are:

1) Flow polytope (also called demand polytope) for multicommodity flow in undirected graphs is within O(log k) of cut as shown in

F. Leighton and S. Rao,“An approximate max-flow min-cut theoremfor uniform multicommodity flow problems with applications to approximation algorithms,” in Proc. of 28th Annual Symposium on Foundations of Computer Science, (Los Alamitos, California), 1988.

N. Linial, E. London, and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications,” Combinatorica, vol. 15, no. 2, pp. 215–245, 1995.

2) Demand polytope of multicommodity flow in directed graphs with symmetric demands is within O(log^2 k) of cut as shown in

P. Klein, S. Plotkin, S. Rao, and E. Tardos, “Bounds on the max-flow min-cut ratio for directed multicommodity flows,” J. Algorithms, no. 22, pp. 241–269, 1997.

3) Max sum-rate in groupcast is within a factor 2 of the multicut. (I don't know a reference for this result. Could someone help me with this? Thanks.)

I would like to know more such positive results affirming flow being close to cut assuming certain structure of the problem (such as undirectedness of graph or symmetric demands, as in above). It would be great if you can give me a one-line summary of the result(s) and a reference of the paper. Thanks.

**Tags:** ds.algorithms, approximation-algorithms, approximation-hardness, max-flow-min-cut, multicommodity-flow

---

## 1 answers

### Answer by username_1 on 2012-02-28. Score: 8

I can recommend my recent paper <http://arxiv.org/abs/1110.6832> on multicommodity flows and cuts in polymatroidal networks; we generalize several known results in standard graphs. Although we do not give a nice table summary we discuss many of the known cases. Some of the results that are not discussed in the paper but are of relevance are those for planar undirected graphs and some special cases. These include the result of
Satish Rao on $O(\sqrt{\log n})$ bound on flow-cut gap and tight bound of $2$ for series-parallel graphs by Chakrabarti-Jaffe-Lee-Vincent and some others. James Lee has several papers on flows and cuts on these graphs and any relatively recent one will discuss the existing literature.


---

