Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.